Осенью 1861 г. Пржевальский приехал в Петербург и блестяще сдал экзамены в Академию Генерального штаба. Во время учебы он по своей инициативе написал «Военно-статистическое обозрение Приамурского края», где собрал все известные данные об Амуре. В Русском географическом обществе на труд, носивший печать явного литературного дарования и таланта подлинного ученого, обратили внимание. Вскоре Пржевальский стал действительным членом общества. Но до путешествий было еще далеко.
По окончании академии будущий путешественник преподавал географию и историю в Варшавском юнкерском училище, где написал учебник «Заметки всеобщей географии по программе юнкерских училищ», получивший общее признание. Этой книгой долгое время пользовались во многих учебных заведениях России и даже в Пекине. Кроме того, здесь он познакомился с ученым-зоологом Тачановским и ботаником Александровичем. Под их влиянием Пржевальский за два года смог получить серьезную научную подготовку и начал подумывать о научной экспедиции в Центральную Азию. Для этого он подал рапорт о переводе в один из восточных военных округов. Однако подозрительный звук «прж» в фа милии после польского восстания вызывал серьезные подозрения у начальства, и долгое время его прошения оставались без ответа. Но настойчивость молодого преподавателя победила. В ноябре 1864 г. пришел приказ о его причислении к Генеральному штабу с назначением «для занятий в Восточно-Сибирский военный округ».
В январе следующего года Пржевальский отправился в Петербург, чтобы получить инструкции в Генеральном штабе и Русском географическом обществе. Здесь он встретился с Семеновым-Тян-Шанским, который заинтересовался планами Николая Михайловича и дал ему рекомендации к западносибирскому губернатору Корсакову и в Сибирское отделение Географического общества. Это помогло: уже в мае 1867 г. Пржевальский отправился в свою первую экспедицию в Уссурийский край, после которой сразу вошел в число крупных исследователей-географов.
В ходе экспедиции были исследованы южная часть края, р. Уссури, оз. Ханка, побережье Японского моря. Собрав богатые коллекции, материалы о природе, климате, жителях края, путешественник вернулся в Иркутск. В общей сложности было пройдено 3 тыс. км, снята на карту значительная территория, изучены пути, ведущие в Маньчжурию и Корею, и пр. Поскольку экспедиция носила не только научный, но и военный характер, отряд участвовал в карательных действиях против китайских разбойников-золотоискателей в Маньчжурии (они вторглись на русскую территорию и сожгли несколько деревень). Пржевальский получил чин старшего адъютанта войск Приамурской области, позже был удостоен серебряной медали Русского географического общества.
Но не чины интересовали ученого-путешественника. Рискуя вызвать неудовольствие начальства, он выступил с сообщением о неблагополучном положении уссурийских казаков. По результатам путешествия написал работы «Инородческое население в южной части Приамурской области» и «Путешествие в Уссурийском крае. 1867–1869 гг.» (книга была издана за свой счет). А в 1870 г. Пржевальский отправился в Петербург для доклада в Русском географическом обществе и Российской академии наук. После этого Семенов-Тян-Шанский сразу же привлек путешественника к разработке плана путешествия в Китай и Монголию.
В то время на карте Азии в центре материка светилось громадное белое пятно площадью более 7 млн кв. км. Здесь не ступала нога ни одного европейского исследователя. По плану Пржевальского предполагалось для начала изучить районы гор Ганьсу, входящих в систему Наньшаня, страну Ордос и Северный Тибет. Часть пути предстояло пройти по району восстания дунган – китайских мусульман, которые еще в 1860-х гг. выступили против цинской (маньчжурской) династии и опустошали целые районы в Монголии, не щадя ни старого, ни малого. Доброжелатели, так же как и Маклая, пугали Пржевальского неизбежной гибелью, но путешественник не испугался. Наоборот, он загорелся идеей собрать сведения о восстании, о котором в Европе почти ничего не было известно.
Первая монгольская экспедиция (так стали ее называть впоследствии) в декабре 1870 г. выступила из Кяхты на Ургу (совр. Улан-Батор). Отсюда через пустыню Гоби добрались до Калгана и двинулись к Пекину. Здесь получили паспорт от китайского правительства и отправились на оз. Далайнор, а потом вернулись в Калган.
В начале мая 1871 г. Пржевальский со своим помощником М. А. Пыльцовым и двумя казаками, взяв 8 верблюдов и двух коней, отправился исследовать Монголию. Маленький отряд двинулся в таинственную страну Ордос у северной излучины р. Хуанхэ, прошел Ордосской степью, пересек южную часть Гоби, взошел на Алашаньские горы, достиг берегов высокогорного оз. Кукунор, известного европейцам только по названию. Накануне 1872 г. отряд вернулся в Калган, завершив первый этап путешествия.