В начале мая следующего года, проделав нелегкий путь в пять тысяч верст на перекладных, а где и пешком, поручик Венюков появился в Иркутске в качестве старшего адъютанта штаба войск Восточной Сибири.
Генерал-губернатор Муравьев предложил ему поехать вместе с ним на Амур. Венюков записал в своем дневнике: «Лучшего поощрения к работе нельзя было бы сделать. Мечта моя быть на Амуре, представлявшем в то время крупный политический интерес, сбывалась».
7 июля 1857 года Венюков увидел широкий полноводный Амур. Ему довелось закладывать город Благовещенск (сейчас центр Амурской области), руководить возведением построек в устье Зеи, участвовать в закладке поста Хабаровка (ныне крупный город Хабаровск). В это же первое путешествие появилось на карте селение Венкжово. «Мне была сделана честь наименованием по моей фамилии одной станицы на Уссури, довольно большой, имеющей теперь церковь и даже школу», — много лет спустя, уже живя в Париже, писал Венюков в своих «Воспоминаниях».
Наконец первая самостоятельная экспедиция. 1 июня 1858 года от Уссурийского поста (ныне Казакевичево возле Хабаровска) отчалили две большие лодки. В них находились «один зауряд-офицер как начальник команды, один переводчик гольдского языка, мой слуга и 12 казаков», — пометил в дневнике путешественник.
Цель экспедиции хорошо выражена в названии отчета о ней — «Обозрение реки Уссури и земель к востоку от нее до моря». По поводу этой работы Венюкова, опубликованной в записках Северо-Восточного отдела Русского Географического общества, его вице-президент выдающийся географ П. П. Семенов-Тян-Шанский писал: «Первым пионером обстоятельного географического исследования почти всего течения реки Уссури был М. И. Венюков. Результатом этого первого русского путешествия вдоль всего течения Уссури была съемка реки и множество расспросных сведений о притоках рек, талантливо сгруппированных и изложенных путешественником в его интересной работе». А вот как пишет об этих, ныне обжитых местах сам первопроходец: «…15 июня мы действительно перешли невысокий хребет, отделяющий реку от берегов океана, и вступили в долину другой реки, текущей в море. Вся пройденная нами местность… до самого перехода в горах представляет непрерывную долину шириной от полуверсты до четырех верст и очень удобную для поселения. Она покрыта преимущественно отдельными группами вязовых и дубовых деревьев, иногда рощицами, которые на горах переходят в сплошные смешанные леса. Чем ближе подходишь к перевалу через горы, тем чаще встречаются, среди берез, ильмов, осин и других лиственных пород, хвойные деревья и отчасти лиственница и ель. Великолепные кедровники достигают здесь особенно исполинского роста…»
Утром 18 июля Венюков со своими спутниками достиг морского берега возле впадения реки Зеркальной. Радостно было думать, что первый шаг в освоении этих русских земель сделан им — молодым ученым. Будущее казалось прекрасным!.
Много путей и дорог придется еще пройти Михаилу Ивановичу. Он будет путешествовать по горам Памира и Тянь-Шаня, по Заилийскому краю, исследовать озеро Иссык-Куль и верховья реки Чу, путешествовать по Кавказу, Турции, Японии и Китаю, служить в Польше и быть секретарем Географического общества в Петербурге. Но куда бы ни забрасывала его судьба, он никогда уже не забывал Дальнего Востока.
Венюков был великим патриотом и гражданином. Он имел острый практический ум, прекрасно видел всю бездарность правителей тогдашней крепостной России, препятствовавших науке. И он не скрывал своего отношения к тем безобразиям, какие творились вокруг. Он выступает в печати в России и за границей, сотрудничает в герценовском «Колоколе». Все это очень не нравится властям. Его начинают травить, создают невыносимые условия для работы, всячески ущемляют.
Сорокалетний полковник Венюков — большой и разносторонний ученый. К этому времени им созданы выдающиеся труды но картографии, естествознанию, физической географии, истории, статистике, этнографии, военной политике. Своими трудами он хочет служить Родине, а его норовят послать на Кавказ руководить каким-то бюрократическим комитетом или командовать артиллерийской частью.
После долгих колебаний Михаил Иванович решает покинуть Россию. Надолго ли? Подобно своему духовному учителю Герцену, Венюков твердо решил остаться русским патриотом и делать все возможное для блага своего народа.
22 сентября 1877 года из Гельсингфорса отправлено письмо императору Александру II. В этом письме Венюков подробно изложил причины, заставившие его уйти в отставку и покинуть Россию. Заканчивалось письмо следующими исполненными высокого достоинства словами: «…можно лишить меня полученных в течение 26 лет внешних отличий, которых суетность мне была всегда совершенно ясна, можно вычеркнуть мое имя из списка русских граждан, но нет силы, которая могла бы исключить меня из числа преданных сын в русской земли. Это, государь, подтверждают гласно даже враги России».