После окончания гимназии в 1855 году Николай решил пойти на военную службу, чтобы принять участие в разразившейся Крымской войне. На службу его взяли, но на войну не отправили. Армейская жизнь не понравилась Пржевальскому – если остальные офицеры тратили свой досуг на карточные игры, то Николай, помня о своей детской мечте стать путешественником, занимался самообразованием. Он увлечённо читал книги по зоологии, ботанике, истории и географии, собирал гербарии, ходил на охоту. Офицеры посмеивались над сослуживцем, но он не обращал на это внимания, упорно двигаясь к своей мечте. Понимая, что самообразования ему недостаточно, Пржевальский поступил в Академию Генерального штаба, блестяще сдав экзамены. Здесь он тоже держался особняком, налегал на науки, занимался теоретической подготовкой к будущим путешествиям. В эти годы вышла его первая научная работа по географии – «Военно-статистическое описание Приамурского края», благодаря которой в 1864 году Пржевальский стал членом Географического общества.

В 1866 году Пржевальский добился перевода в только что созданный штаб Восточно-Сибирского военного округа. Перед отправкой к новому месту службы он встретился в Петербурге со знаменитым путешественником Петром Семёновым-Тян-Шанским. Пржевальский несколько самонадеянно для молодого человека изложил ему свои планы путешествия в Центральную Азию и попросил содействия со стороны русских академиков. Понятно, что выделять деньги под планы никому толком не известного молодого офицера никто бы не стал. Однако молодой человек так понравился Семёнову, что тот обещал, что «если он (Пржевальский) на собственные средства сделает какие бы то ни было интересные поездки и исследования в Уссурийском крае, которыми докажет свою способность к путешествиям и географическим исследованиям, то по возвращении из Сибири он может надеяться на организацию со стороны Общества под его руководством более серьёзной экспедиции в Среднюю Азию».

Даже дорогу к месту службы Николай Михайлович воспринял как увлекательное путешествие, о котором оставил восторженные отзывы. «Сибирь совсем меня поразила: дикость, ширь, свобода бесконечно мне понравились», – писал он. Прибыв весной 1867 года в Иркутск, Пржевальский был тепло встречен начальником штаба сибирских войск и по совместительству председателем Сибирского отдела Русского географического общества генералом Кукелем. В мае 1867 года он командировал Пржевальского в Уссурийский край, который был присоединён к России всего несколько лет назад. По оценке Пржевальского, это была командировка в «наиболее интересную часть наших амурских владений», в ходе которой он должен был собрать данные о проживающих на реке Уссури корейцах и маньчжурах, а также изучить пути, ведущие к границам Маньчжурии и Кореи. Помимо этого Пржевальский проводил научные исследования: изучал климат и строение земной поверхности края, его животный и растительный мир, знакомился с жизнью местного населения.

В Иркутске Пржевальский целыми днями сидел в библиотеке, изучая документы, которые относились к Уссурийскому краю. Так он получил необходимые знания для экспедиции: едва взглянув на растение или птицу, мог сказать, водятся они в европейской части России или нет, что упоминали о них его предшественники, изучавшие природу Сибири. Также Пржевальский научился превосходно делать чучела животных и высушивать растения для гербария.

Но даже самому подготовленному путешественнику нужны помощники. Изначально Пржевальский взял с собой одного учёного немца из Варшавы, но тот, добравшись до Иркутска, отказался ехать дальше, испугавшись трудностей. В штабе Пржевальский случайно познакомился с 16-летним топографом Николаем Ягуновым. Способный юноша очень понравился Пржевальскому, и он пригласил его с собой в путешествие, обучив всему необходимому.

Подготовка к экспедиции не заняла много времени, с собой взяли только маршрутные карты, термометр и компас. Зато охотничьей дроби взяли вдоволь – целых 4 пуда (65,5 килограмма), ведь в пути планировали не только добывать шкурки животных для коллекции, охота должна была обеспечивать экспедицию пропитанием.

26 мая путешественники отправились в дорогу. Позже Пржевальский написал в своей книге: «Дорог и памятен для каждого человека тот день, в который осуществляются его заветные стремления, когда после долгих препятствий он видит, наконец, достижение цели, давно желанной. Таким незабвенным днём было для меня 26 мая 1867 года, когда, получив служебную командировку в Уссурийский край, я выехал из Иркутска по дороге, ведущей к озеру Байкалу и далее через всё Забайкалье к Амуру».

Переплыв озеро Байкал на пароходе, Пржевальский и Ягунов за несколько дней проехали на почтовых тройках почти тысячу километров, пересекли Забайкалье и прибыли в город Сретенск на реке Шилке. Здесь они сели на пароход, намереваясь на нём добраться до Амура. Но пароход сломался, чему Пржевальский даже обрадовался и тут же решил плыть дальше самостоятельно на лодке. Это позволяло останавливаться в любом месте, где они замечали что-либо интересное. Дальше пароходом добрались до Хабаровска, откуда и началось путешествие по Уссурийскому краю.

В Хабаровске Пржевальский купил лодку, на которой исследователи отправились вверх по течению реки Уссури. Пока сам Пржевальский вместе с Ягуновым шёл берегом, собирая гербарии, подстреливая интересные экземпляры птиц для коллекции, проводя топографическую съёмку и метеорологические наблюдения, лодка в это время медленно плыла против сильного течения. В ней сидели и изо всех сил работали вёслами казаки, которых Пржевальский нанимал в местных станицах. Прибыв вечером в очередную станицу или разбив лагерь на берегу реки, путешественники сушили растения и делали чучела из птиц. Перед сном Пржевальский записывал события прошедшего дня в своём дневнике.

Нанятые гребцы-казаки с удивлением поглядывали на чудаковатого офицера и не понимали смысла его странной «царской службы». На рассвете небольшой отряд отправлялся дальше.

Уссурийские леса произвели на учёного огромное впечатление. В отличие от Сибирской тайги они переполнены самыми разнообразными видами растений. «Как-то странно непривычному взору, – писал Пржевальский, – видеть такое смешение форм севера и юга, которые сталкиваются здесь как в растительном, так и в животном мире. В особенности поражает вид ели, обвитой виноградом, или пробковое дерево и грецкий орех, растущие рядом с кедром и пихтой. Охотничья собака отыскивает вам медведя или соболя, но тут же рядом можно встретить тигра…» Лишь в одном уссурийская тайга походила на сибирскую. Огромные тучи гнуса – комаров, слепней, мелкой мошки – ужасно мешали исследованиям. Для того чтобы хоть ненадолго присесть и спокойно изучить какое-нибудь растение, нужно было развести костёр с большим количеством дыма.

За 23 дня путешественники преодолели 509 км пути. Добравшись до реки Сунгачи́, по ней на пароходе доплыли до большого озера Ханка, которое находится на границе между Китаем и Россией. С севера на юг оно простирается на 95 километров. Весь август Пржевальский со своими спутниками изучал богатый растительный и животный мир озера – его поразило огромное количество цветков лотоса, покрывавших водную гладь, а также обилие и разнообразие местной рыбы.

В начале сентября Пржевальский отправился на юг к Новгородской бухте,