В 1845 году, учитывая нелегкое материальное положение семьи, родители решили определить тринадцатилетнего сына «на казенные хлеба» в кадетский корпус в Петербурге. Блестяще сдав вступительные экзамены, он был принят сразу во второй класс. В годы пребывания в корпусе юный кадет старательно занимался естественными науками, увлекался «Космосом» Гумбольдта. Читал передовую литературу 1840-х годов: философские «Письма об изучении природы» и художественные произведения «Кто виноват?», «Доктор Крупов» Герцена, переписку Белинского с Гоголем, исторические статьи Грановского. Эти произведения, как писал впоследствии Венюков, «сохранились в памяти многих моих сверстников. И никто не станет отрицать благотворного влияния их на свое развитие, никто не бросит камнем в их авторов, стоявших на таком высоком уровне нравственной чистоты и работавших так неустанно в пользу света среди окружавшей их тени. Благородные, светлые личности, незабвенные в русской истории».
Выпущенный из корпуса в чине прапорщика Венюков с 1850 года начал профессиональную военную службу в артиллерийской батарее в Серпухове. Продолжая много читать, он переписывает от руки в 1851 году роман Герцена «Кто виноват?», на всю жизнь ставший для него реликвией. Не переставал артиллерийский прапорщик заниматься и естественными науками. В Серпухове он написал свои первые научные заметки. В 1853 году Венюкова отзывают в Петербург и назначают репетитором по физике в его родном кадетском корпусе. Оказавшись в столице, он стал сразу же ходатайствовать о допущении его вольнослушателем в университет. Получив разрешение, Венюков слушал лекции П.Л. Чебышева и В.Я. Буняковского по математике, С.С. Куторги по зоологии, Э.Х. Ленца по физике, И.И. Ивановского по международному праву. Но в августе 1854 года, не дослушав университетского курса, Венюков поступил в николаевскую Академию Генерального штаба, которую успешно закончил в 1856 году.
В конце того же 1856 года двадцатичетырехлетний офицер получил назначение в штаб генерал-губернатора Восточной Сибири Н.Н. Муравьева-Амурского – одного из самых колоритных российских «проконсулов», высоким покровительством которого пользовался даже такой знаменитый бунтарь, как Михаил Бакунин в пору своей сибирской ссылки. Вскоре по прибытии к Муравьеву Венюков отправился в свое первое путешествие, получив предложение от самого генерал-губернатора о поездке вместе с ним на Амур. «Лучшего поощрения к работе нельзя было придумать, – писал впоследствии Михаил Иванович. – Мечта моя быть на Амуре, представлявшем в то время крупный политический интерес, сбывалась…»
Путешествие по Амуру стало лишь начальным этапом в исследовании Венюковым Дальнего Востока. В 1858 году ему было поручено организовать и провести первую русскую экспедицию вдоль всего течения реки Уссури. С маленьким отрядом казаков Венюков тщательно обследовал бассейн реки, первым из русских перешел Сихотэ-Алиньский хребет и вышел к Японскому морю, составив подробное научное описание Уссурийского края и положив начало изучению этих земель.
В годы пребывания в Восточной Сибири Венюков близко сошелся с тамошней интеллигенцией, группировавшейся вокруг сибирского отдела Русского географического общества. Он был знаком с М.А. Петрашевским, которого высоко оценил в своих воспоминаниях: «Ум многосторонний, резко аналитический и в то же время глубоко сочувствовавший всему гуманному без фальши, без экивоков, не склоняясь ни перед чьим авторитетом».
В 1859–1860 годах старшего адъютанта в штабе Отдельного Сибирского корпуса Венюкова занимают уже другие, отдаленные и малоизвестные территории России. Сначала он возглавляет разведывательную экспедицию в долину реки Чу, а затем руководит геодезическими съемками на озере Иссык-Куль. Итоги проделанной работы вылились в обширную научную публикацию, удостоенную серебряной медали Русского географического общества.
В 1861–1863 годах Венюков служит на Северо-Западном Кавказе в должности командира батальона Севастопольского пехотного полка. Одним из результатов предпринятого им изучения истории, этнографии и статистики этого края стало составление его первой этнографической карты.
В конце 1863 года Венюкова переводят на службу в Польшу, где с апреля следующего года он становится председателем Люблинской комиссии по крестьянским делам. В ту пору Н.А. Милютин и его сподвижники проводили в «замиренной» Польше аграрную реформу на гораздо более выгодных для крестьян условиях, чем в самой России. Параллельно с активным участием в делах реформы Венюков успевает написать учебник по физической географии, который увидел свет уже в 1865 году. В начале 1867 года Михаил Иванович получил отпуск от службы с сохранением за ним прежнего жалованья в течение двух лет. Это дало ему возможность приступить к осуществлению давней мечты «о путешествии по Европе, а может быть, и вокруг света».