Далее отряд двинулся в совершенно неизведанные края, к берегам Хуанхэ – Жёлтой реки. Здесь начались настоящие трудности. Бóльшую часть пути приходилось идти по южной окраине пустыни Гоби, этим путём не проходил ещё ни один европеец. Путешественников мучили поднимавшие целые тучи пыли песчаные бури, сильнейший ветер, от которого болела голова, непереносимые дневной жар и ночной мороз. Особенно тяжело было без пресной воды. Пржевальский так описывал воду, из которой приходилось варить чай: «Возьмите стакан чистой воды, положите туда чайную ложку грязи, щепотку соли, извести для цвета и гусиного помёта для запаха – и вы как раз получите ту прелестную жидкость, которая наполняет здешние озёра». Питались путешественники мясом убитых на охоте животных и местной крупой – дзамбой, о которой Пржевальский отзывался так: «Свиней у нас лучшей посыпкой кормят. После еды, через час, дзамба разбухает в желудке, и, зная это, мы едим подобную прелесть не чересчур».
Пржевальский впервые познакомился со всеми трудностями горной охоты. Взбираясь по отвесным скалам, охотник сильно устаёт. Руки нетвёрдо держат ружье, прицеливаться становится всё сложнее. К тому же глубокие ущелья грозят гибелью на каждом шагу.
Местные жители относились к путешественникам настороженно, подозревая в них шпионов: не пускали на ночлег, обманывали при продаже припасов, отказывались показывать дорогу или указывали неправильное направление. Бывало, отряду Пржевальского приходилось преодолевать впустую десяток или более километров в противоположную сторону от нужного направления. И когда дорогу преграждали отвесные скалы, приходилось с досадой возвращаться обратно.
К 11 июня отряд Пржевальского переправился на плоскодонных баркасах через реку Хуанхэ и вступил на пустынное плато Ордос. Подробно нанеся течение Хуанхэ на карту, в начале сентября добрались до наиболее дикой и бесплодной части Гоби – пустыни Алашань, в которой «не может существовать почти никакая живая тварь». На сотни километров тянулись «голые сыпучие пески, всегда готовые задушить путника своим палящим жаром или засыпать песчаным ураганом». Несмотря на все сложности в середине сентября путешественники добрались до Алашаньских гор. Здесь находится единственный среди пустыни город Дынь-юань-ин (современный Яньянь). Местные монгольские чиновники, узнав, что Пржевальский не миссионер, приняли отряд приветливо. Градоначальник разрешил поохотиться в Алашаньских горах на баранов. До заветного озера Кукунор оставалось всего 640 км и около месяца пути. Однако Пржевальский решил вернуться в Пекин. Деньги, выделенные на экспедицию, подходили к концу, и к тому же выяснилось, что выданные китайским правительством документы не давали разрешения путешествовать по западным провинциям. «С тяжёлой грустью, понятной лишь для человека, достигшего порога своих стремлений и не имеющего возможности переступить через этот порог, – писал Пржевальский, – я должен был покориться необходимости и повернул в обратный путь». Из-за недостатка денег и продовольствия отряду предстояло пройти 1300 километров без остановок. На обратной дороге им удалось изучить не исследованную еще область на правом берегу Хуанхэ. В тех самых местах, где они летом мучились от сильной жары, теперь, в ноябре, стояли морозы до минус тридцати, с сильнейшими ветрами. «Климат – самый подлый, какой только можно вообразить», – писал Пржевальский.
Редкая ночь проходила спокойно. Бродившие кругом волки подбирались к верблюдам и лошадям. Монгольские собаки прибегали воровать мясо, норовили забраться даже в палатку. Приходилось вылезать из-под шкур и выстрелами отпугивать хищников. Просыпались верблюды и вскакивали, испуганные. Нужно было снова уложить их. После этого не скоро удавалось согреться.
Однажды ночью пропали все верблюды – вероятно, их украли. На поиски ушло несколько дней, но животных не нашли. Лошадей нечем было кормить, а местные жители ничего не продавали. Одна из истощённых от голода лошадей замёрзла ночью. У отряда осталась единственная лошадь. Экспедиция оказалась на грани гибели. С большим трудом Пржевальский уговорил местных жителей продать ему новую лошадь и отправил на ней казака в ближайший город Кукухото, чтобы тот на последние деньги купил верблюдов что, к счастью, удалось. Из-за этого происшествия отряд потерял 17 дней. И всё-таки в конце декабря 1871 года они благополучно добрались до города Калган, где их встретили русские купцы. Первая часть путешествия закончилась. Оставив весь состав экспедиции в Калгане, Пржевальский поспешил в Пекин за деньгами и новыми документами.