Сразу же по прибытии в Иркутск Пржевальский возбудил перед начальством вопрос о командировании его в Уссурийский край для проведения военно-статистических исследований. Собственно говоря, идея такой поездки принадлежала председателю ИРГО П.П. Семенову, который, отказав Пржевальскому в материальной помощи, счел нужным поддержать многообещающего офицера морально и снабдил Николая Михайловича рекомендательными письмами к восточносибирскому генерал-губернатору М.С. Корсакову и начальнику штаба войск Восточной Сибири генералу Б.К. Кукелю. Семена инициативы упали на благодатную почву: несмотря на труды Р.К. Маака, М.И. Венюкова, К.Ф. Будогоского и других первопроходцев, Уссурийский край по-прежнему представлял собой огромное белое пятно. Особенно нужны были сведения о путях сообщения Приморья и состоянии поселений — как русских, так и «инородческих», — расположенных на его территории. В начале мая 1867 г. Николай Михайлович получил инструкции иркутского штаба и спустя двадцать дней выехал на Амур.
Несмотря на отсутствие у Пржевальского опыта длительных путешествий, его первая экспедиция оказалась исключительно удачной. Начало осени 1867 г. застало штабс-капитана и его немногочисленных спутников в посту Камень-Рыболов на озере Ханка. Только естественнонаучные изыскания путешественника на Уссури и озере Ханка за два летних месяца дали 1200 образцов растений, 10 звериных шкур, 60 чучел птиц, 22 из которых принадлежали неизвестным ранее видам. Удалось собрать солидную коллекцию насекомых и даже открыть неизвестный вид млекопитающего — черного зайца. Не забывал Пржевальский и о военных задачах своей поездки. Сбором «военно-статистических сведений» об Уссурийском крае предстояло заняться в оставшееся время. 29 августа 1867 г. экспедиционный отряд в составе Н.М. Пржевальского, помощника-препаратора НЯ. Ягунова и двух солдат выступил из Камень-Рыболова на реку Суйфун. Начиналось путешествие, призванное дать правительству ясную картину заселения нового края, оценить его пригодность для передвижения и расквартирования войск, наметить перспективы его развития. Здесь Пржевальский был пионером: все экспедиции, посещавшие Приморье до него, работали в полосе, прилегающей к русско-китайской границе, и не затрагивали внутренних районов края. Исключением были две экспедиции А.Ф. Будищева, организованные Министерством государственных имуществ (в 1859 и 1866 гг.), однако этот исследователь преследовал специальную цель — изучение приморских лесов.
Поход партии Пржевальского по Уссурийскому краю продолжался до начала 1868 г. 7 декабря усталые и обносившиеся путешественники добрались до залива Святой Ольги. Побывав на реках Цемухэ и Сучан и посетив только что основанные в этих местах русские деревни Шкотову, Владимирскую и Александровскую, Пржевальский поразился бедности поселенцев, с трудом привыкающих к незнакомой природе азиатской окраины. Уже тогда путешественнику бросилось в глаза откровенно недружественное отношение к русским уссурийских китайцев — «манз».
Отдохнув в Ольгинском посту и пополнив походные запасы, путешественники вновь отправились в путь. 18 декабря отряд достиг долины реки Тазуши, густо заселенной «манзами». Как раз в это время на Сучанe начинались китайские волнения, которым спустя несколько месяцев предстояло разгореться в пламя «Манзовской войны»… С берегов Тазуши Пржевальскому и его спутникам предстоял 80-верстный переход через главный хребет Сихотэ-Алиня в верховья реки Лифудин. Экспедиция столкнулась с самыми тяжелыми испытаниями. Столбик термометра опускался ниже отметки 30 градусов, полуметровый слой снега замедлял движение отряда, изматывая людей и животных. Одна из лошадей «издохла от натуги», другая утонула при переправе через реку…
Конечной целью Пржевальского была станица Бельцова в месте слияния рек Даубихэ и Улахэ, дающих начало Уссури. Таким образом, к Новому году Николай Михайлович надеялся достигнуть знакомых мест и замкнуть маршрут своего путешествия. Начавшаяся 30 декабря сильная метель похоронила все планы и заперла путников в убогой китайской фанзе. Здесь, при свете тусклого жирника, «среди грубых и невежественных манз», Пржевальскому пришлось отметить наступление богатого событиями 1868 г. В Бельцову экспедиция пришла только несколько дней спустя, а конечным пунктом экспедиции стала станица Буссе. За время пути Николай Михайлович нанес на карту многочисленные таежные тропы, сделал ценные этнографические наблюдения и провел первую в Уссурийском крае перепись поселенцев, охватившую 1259 человек.