Венюкову была поручена срочная работа по составлению топографических карт и анализу военной статистики для полной оценки политической ситуации на Дальнем Востоке с целью его дальнейшего заселения. Данные были необходимы генерал-губернатору для личного доклада в Петербурге. Следом за Муравьевым курьерская тройка за десять дней доставила в столицу и его адъютанта. Недолгое пребывание в Петербурге запомнилось М.И. Венюкову встречей и долгой беседой с героем Амурской экспедиции Г.И. Невельским.
В феврале 1858 г. М.И. Венюков уже снова был в Иркутске и вскоре начал подготовку к своей первой экспедиции: по Уссури, через Сихотэ-Алинь к океану. Волею судьбы в мае 1858 г. ему довелось присутствовать при подписании Айгунского трактата и участвовать в закладке поста Хабаровка. А 1 июня 1858 г. М.И. Венюков со своими спутниками – сотником Пешковым, переводчиком Масленниковым, унтер-офицером Кармановым, денщиком и одиннадцатью казаками – начали свой путь от станицы Казакевичево, что расположилась рядом с только что основанной Хабаровкой.
Путешествие, совершенное двадцатишестилетним офицером, было своего рода подвигом: более 700 км от устья Уссури до перевала через Сихотэ-Алинь он прошел пешком, ведя счет шагам, чтобы карта, составленная им, «не оставляла в недоразумении тех, которые бы стали впоследствии руководствоваться ею». Так был проложен первый пеший маршрут от Хабаровки через Сихотэ-Алинь к Тихому океану.
Выйдя к морю, Венюков собирался продолжить путь к Владимирскому посту, но заболел и вынужден был возвратиться обратно по прежнему маршруту. В пути он переписал начисто свой экспедиционный отчет. Работа называлась «Описание реки Уссури и земель к востоку от нее до моря». Н.Н. Муравьев-Амурский остался очень доволен выполненной М.И. Венюковым работой.
В марте 1859 г. Венюков выступил в Петербурге в Русском географическом обществе с докладом о своем путешествии по Уссури. Сведения, представленные им, получили высокую оценку собравшихся и, в частности, вице-председателя общества П.П. Семенова (с 1906 г. – Тян-Шанский).
В 1860—1870-е гг. М.И. Венюков совершил путешествия по зарубежному Дальнему Востоку, Японии и Китаю, побывал в Средней Азии – в верховьях реки Чу и на озере Иссык-Куль, служил на Кавказе и в Польше.
Картография, естествознание, физическая география, история, статистика, этнография, военная политика находили самое широкое отражение в его работах. В течение двух лет он был секретарем Императорского Русского географического общества, редактировал «Известия» ИРГО. В 1875 г. был участником Международного географического конгресса в Париже.
