Завершая своё выступление Пржевальский сказал о дальнейших планах: «Я получил назначение совершить экспедицию в Северный Китай, в те застенные владения Небесной империи, о которых мы имеем неполные и отрывочные сведения...»

Оставалось только получить китайский паспорт, который позволил бы совершать переходы по отдалённым провинциям Китая. Но для того, чтобы добраться до властей в Пекине, необходимо было уже начать великое путешествие: только до Иркутска — пять тысяч вёрст и больше тысячи — от пограничного селения Кяхта до китайской столицы. Пржевальский взял с собой своего бывшего ученика, выпускника Варшавского училища Михаила Пыльцова. В Сибири к ним присоединились два казака. Вчетвером путешественники пересекли великую пустыню Гоби.

Начиналась зима, стояли тридцатиградусные морозы, сопровождавшиеся жестоким ветром. «Глубокая зима с сильными морозами и бурями, — записывал Пржевальский, — полное лишение всего, даже самого необходимого, наконец, различные другие трудности, — всё это день в день изнуряло наши силы. Жизнь наша, в полном смысле, — борьба за существование, и только сознание научной важности предпринятого дела давало нам энергию и силы для успешного выполнения задачи. Сидеть на лошади невозможно от холода, идти пешком также тяжело...»

После промороженной пустыни совсем другим миром показался по-весеннему тёплый город Калган (сейчас — Чжанцзякоу). Здесь путешественники закупили продукты, но не очень много: по мешку риса и проса, пуд сахара. Пржевальский, как и в первом путешествии, надеялся в основном на охоту. Он вспоминал о своём детстве: «...Я рано пристрастился к охоте. Сначала стрелял я из игрушечного ружья желудями, потом из лука, а лет двенадцати получил настоящее ружьё...»

Из Калгана исследователи двинулись караванным путём, по которому уже давно никто не ходил после того, как банды дунган разорили все окрестные деревни: «Следы дунганского истребления встречались на каждом шагу... и нигде не было видно ни одной души».

Первым объектом топографической съёмки стало озеро Далайнор, принимающее воды монгольской реки Керулен. Когда во время летнего половодья поднимается уровень озера, из него идёт сток в реку Аргунь, образующей при слиянии с Шилкой Амур, на котором уже побывал Пржевальский.

Лето прошло в верховье Хуанхэ и на высоком плато Ордос, наполовину засыпанном песками. На юге плато переходило в лёссовую равнину, изрытую гигантскими оврагами, глубиной в 100—150 метров. «Тяжело становится человеку в этом песчаном море... безжизненность и мёртвая тишина вокруг...» Столь же мрачная картина наблюдалась в пустыне Алашань, пески которой «душат путника своим палящим жаром». За быстро промелькнувшим летом наступила зима, жара сменилась стужей. Отряд повернул обратно. По пути были открыты и исследованы два хребта к северу от Жёлтой реки (Хуанхэ). Новый, 1872 год встречали в Калгане, из которого пришлось снова идти в Пекин. Там Пржевальский получил дополнительные средства на дальнейший путь и заменил двух казаков, не очень хорошо показавших себя в трудных переходах, на новых, присланных из Урги. Свежие верблюды пополнили караван. Как только настала весна, цепь навьюченных верблюдов снова появилась в песках безводной пустыни Алашань. Переход оказался очень тяжёлым из-за жары и нехватки воды.

Вода появилась, когда подошли к могучему хребту Алашань. Пржевальский поднялся на самую высокую вершину хребта и увидел внизу хаос горных хребтов, долин, плоскогорий: «Сила впечатления была так велика, что я долго не мог оторваться от чудного зрелища, долго стоял, словно очарованный, и сохранил в памяти этот день как один из счастливейших в моей жизни».

Два года об отряде Пржевальского ничего не знали ни в Петербурге, ни в Пекине. В Географическом обществе стали уже готовить большую спасательную экспедицию, запросили на неё средства у правительства.