Крестным отцом и наставником молодого исследователя явился крупнейший знаток Дальнего Востока Геннадий Иванович Невельской. «Он лично навестил меня в скромной моей квартире в одной из отдаленных частей Петербурга, — пишет Венюков, — пригласил к себе, в течение нескольких вечеров беседовал со мною о Нижне-Амурском и Уссурийском краях, о которых имел обширные сведения… Более честного человека мне не случалось встречать, и хотя его резкость, угловатость могли иногда не нравиться, но всякий, кто имел случай ближе подойти к нему, скоро замечал, какая теплая, глубокосимпатическая натура скрывалась за его непредставительной наружностью».
От Невельского Венюков перенял гражданственное отношение к науке, уменье направлять свои усилия на решение наиболее актуальных задач. А потом он уже сам передавал эту традицию будущему корифею русской географии Н. М. Пржевальскому. В частности, к советам Венюкова Николай Михайлович Пржевальский прислушивался при выборе своих маршрутов по совершенно диким и не исследованным местам Центральной Азии. Между обоими путешественниками завязалась многолетняя дружеская переписка. Это один из примеров того, как сливалась в единое целое выдающаяся русская географическая школа.
Во второй половине апреля 1858 года Венюков вновь на Амуре. Год этот принес с собой перелом в пограничном вопросе. По Айгунскому договору, подписанному 28 мая 1858 года Муравьевым и китайским главнокомандующим И Шанем, и последовавшему за ним в 1860 году Пекинскому договору, между двумя великими державами была проложена существующая и поныне государственная граница. Старые русские земли Приамурья по обоюдному согласию, достигнутому путем мирных переговоров, были окончательно закреплены за Россией. Россия прочно утверждалась на Тихоокеанском побережье, а Китай был защищен с севера от проникновения заклятых своих врагов — английских, французских, американских и других экспансионистов.
М. И. Венюков передает некоторые подробности подписания Айгунского договора, заключенного в исключительно краткий для дипломатии срок: 25 мая Муравьев появился в Айгуне, а 28 мая договор был уже заключен. После подписания договора китайские представители признавались, «что их удивила умеренность наших требований, что они ожидали для начала негоциаций (дипломатических переговоров. — А. С.) домогательства нашего на все земли до Великой стены и Желтой реки в Ордосе, дабы потом, по принятому в дипломатии обычаю, сбавлять эти требования».
Как известно, уже тогда англичане и французы признавали только один язык в разговорах с Китаем — язык пушек… В Айгуне же все вопросы были решены при полном согласии обеих договаривающихся сторон. О другой любопытной детали переговоров сообщил Г. И. Невельской. В первоначальном проекте договора говорилось, что он заключается «ради большей славы и пользы обоих государств». На это китайский делегат заявил:
«Не надобно упоминать эти слова, ибо зачем тут упоминать о славе, когда наше государство и без того так славно, что большей славы ему желать нельзя». По его предложению это выражение было заменено на другое: «Ради большей, вечной взаимной дружбы обоих государств».
Эти слова и вошли в договор.
В день, когда завершились переговоры Муравьева с китайскими представителями о границе, Венюков с капитаном Дьяченко и солдатами 13-го линейного батальона был уже в районе будущего Хабаровска. Здесь он участвовал в закладке поста Хабаровка и готовился к экспедиции на Уссури.
Предстояло с суши обозреть русское Приуссурье, найти перевалы к морю через мощные Сихотэ-Алинские хребты. Венюков как раз и выполнил эту задачу. Путешествовавший по тем же местам академик К. И. Максимович нашел маршрут Венюкова «составленным чрезвычайно добросовестно». Знаток Дальнего Востока В. К. Арсеньев с чувством признательности к своему предшественнику отмечал: «Честь сделать первое пересечение через Сихотэ-Алинь принадлежит М. И. Венюкову».
Результатом экспедиции явилось «Обозрение реки Уссури и земель к востоку от нее до моря». В этом очерке показана физическая география вновь открытого края, представлен быт его крайне редкого населения. Со страниц отчета, написанного патриотом, зазвучал горячий призыв к русским людям: заселяйте Уссурийский край, берите богатые дары его природы!
«Первым пионером обстоятельного географического исследования почти всего течения р. Уссури был М. И. Венюков, — писал по поводу этой работы вице-президент Русского Географического общества выдающийся географ П. П. Семенов-Тан-Шанский. — Результатом этого первого русского путешествия вдоль всего течения Уссури была съемка реки и множество расспросных сведении о притоках реки, талантливо сгруппированных и изложенных путешественником в его интересной статье «Обозрение р. Уссури».