К этому времени он, наконец, добился перевода в Восточную Сибирь. Уже в Иркутске, с помощью рекомендательных писем Семенова он выхлопотал двухлетнюю служебную командировку в Уссурийский край. Кроме того, опять же не без помощи Семенова, Сибирский отдел географического общества предписывает Пржевальскому изучить флору и фауну края, собрать ботаническую и зоологическую коллекции.
Со своим спутником - юношей Ягуновым - он спустился по Амуру, плавал на лодке по Уссури, пробирался тропами неведомого края.
Два с половиной года провел Пржевальский на Дальнем Востоке. Тысячи километров пройдены, 1600 километров покрыты маршрутной съемкой. Бассейн Уссури, озеро Ханка, побережье Японского моря... Подготовлена к печати большая статья "Инородческое население Уссурийского края". Собрано около 300 видов растений; изготовлено более 300 чучел птиц, причем многие растения и птицы на Уссури обнаружены впервые. Он начинает писать книгу "Путешествие в Уссурийском крае".
В январе 1870 года Николай Михайлович вернулся в Петербург, в марте впервые взошел на трибуну Русского географического общества.
Он рассказывал об Уссурийском путешествии и о своих дальнейших планах. Его описание Уссурийского края раскрыло такие картины в жизни природы и русских переселенцев, что слушавшие его поражались: как это было возможно - работая в одиночестве, если не считать мальчика-препаратора, собрать такие глубокие, обширные сведения... В результате ему была присуждена Серебряная медаль.
В 1870 году Русское географическое общество организовало экспедицию в Центральную Азию. Начальником ее был назначен офицер Генерального штаба Пржевальский.
В сентябре 1870 года Пржевальский отправился в первую свою экспедицию в Центральную Азию. Вместе с ним ехал бывший его ученик по Варшавскому училищу подпоручик Михаил Александрович Пыльцов. Их путь лежал через Москву и Иркутск и дальше - через Кяхту в Пекин, где Пржевальский рассчитывал получить в китайском правительстве паспорт - официальное разрешение на путешествие в области, подвластные Небесной империи.
Получив паспорт, Пржевальский выезжает в Тибет. Небольшому каравану из восьми верблюдов, несущих экспедиционное снаряжение, предстоит преодолеть огромный путь.
Великая пустыня Гоби встретила их 30-градусными морозами с ветрами. Они преодолели пустыню, перевалили через горный хребет и в декабре вошли в город Калган, где царила настоящая весна. Путешественники пополнили запасы провизии, хотя рассчитывали в основном на охоту, проверили револьверы и ружья. Пржевальский избрал караванный путь, по которому, опасаясь нападения разбойничьих шаек, уже в течение одиннадцати лет не осмеливался пройти ни один караван.