В 1856 г. Пржевальский был произведен в прапорщики и переведен в Полоцкий полк, где занимался охотой, сбором гербария и чтением книг. В это время мир был взбудоражен географическими открытиями в Африке и Южной Америке, П. П. Семенов открыл для мира новую горную страну на южных рубежах России – Тянь-Шань… А здесь – идиотство военной службы. Не о том мечтал будущий путешественник. Он подает прошение о переводе на Амур. Получает отказ и понимает, что единственная возможность вырваться из порочного круга – дальнейшее военное образование в Академии Генерального штаба.

Разрешение приходит только в 1861 г. Экзамены были сданы на «отлично», и опостылевшая армейская служба осталась позади. Уже на втором курсе Пржевальский пишет работу «Военно-географическое обозрение Приамурского края», за которую в 1864 г. его принимают в Русское географическое общество. Но перед этим, в 1863 г., состоялся досрочный выпуск слушателей академии (в связи с восстанием в Польше), и Н. М. Пржевальский в чине поручика снова отправляется в Полоцкий полк, где посвящает много времени ботанике, зоологии, географии, не оставляя мысли о будущих исследованиях новых земель. В конце 1864 г. по ходатайству друзей его назначают в Варшавское юнкерское училище дежурным офицером и преподавателем истории и географии. В своем «Автобиографическом рассказе» он написал об этом периоде своей жизни: «Здесь в течение двух лет и нескольких месяцев я в уверенности, что рано или поздно, но осуществлю заветную мечту о путешествии, усиленно изучал ботанику, зоологию, физическую географию и пр…»

Только в конце 1866 г. состоялось назначение Пржевальского в штаб Восточно-Сибирского военного округа в Иркутске и одновременное зачисление офицером Генерального штаба. В январе 1867 г. он прибывает из Варшавы в Санкт-Петербург, где в географическом обществе встречается с П. П. Семеновым для обсуждения перспектив экспедиции в Центральную Азию. Семенов советует будущему путешественнику сначала испробовать свои силы в малоизученном Уссурийском крае, недавно присоединенном к России.