В разгар подготовки пришло письмо из Парижа с сообщением о присуждении Пржевальскому Золотой медали Парижского географического общества. Звали приехать хоть на несколько дней, но он никак не мог — сборы. Лишь выбрался на шесть дней в своё имение на Смоленщине, чтобы встретиться с друзьями и поохотиться. Эта поездка для Пржевальского была важнее парижской. В имении он окончил 2-й том книги о путешествии в Монголию и страну тангутов.

Жарким июньским днём 1876 года Пржевальский выехал с провожавшим его Пыльцовым из Москвы в Нижний Новгород по железной дороге с багажом 130 пудов. На всякий случай он отправил из Перми Пыльцову своё духовное завещание, но в письме добавил: «Впрочем, мне кажется, всё обойдётся благополучно, и мы все возвратимся через три года. Конечно, здоровья поубавится, да и седых волос прибудет».

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

В этом азиатском городе пришлось провести несколько недель, сортируя снаряжение: что-то оставить, что-то просушить (по дороге опрокинулся в реку тарантас с десятком ящиков). В Кульдже закуплено было 24 верблюда и 4 лошади.

Через туркестанского генерал-губернатора К.П. Кауфмана Пржевальский получил письмо тамошнего властителя эмира Якуб-бека. Он писал, что примет экспедицию, как гостей. Пришло и предупреждение: весь южный склон Тянь-Шаня занят восставшими против власти Китая тангутами, и китайское правительство не берёт на себя охрану путешественников.

Тем не менее экспедиция двинулась дальше, по долине реки Или, которую Пржевальский назвал «азиатской Ломбардией по своему климату и плодородию». Поднявшись на высокое плато Юлдус у подножия хребта Нарат, в самом центре Тянь-Шаня, Пржевальский вынужден был отправить назад одного из своих помощников Павало-Швейковского, показавшего полную непригодность к экспедиционной жизни. Из помощников остался, наряду с семью казаками, лишь препаратор Фёдор Эклон. О нём Николай Михайлович писал Пыльцову: «Птиц делает хорошо, всё остальное исполняет как нельзя лучше. С ним вдвоём мы и совершим всю экспедицию».

На некоторое время отряд задержали мусульмане-торгоуты, пославшие гонца в Кашгар к Якуб-беку за разрешением пропустить русских. Ответ пришёл через семь дней. К каравану приставили конвой, и провожатый повёл экспедицию к Лобнору окружным путём — с переправой через реку Тарим.

Между тем уже наступил декабрь, морозы ночью доходили до -22°. С верблюдами было трудно идти по долине Тарима, поросшей лесом и колючим кустарником. Выйдя к берегу озера Лобнор, оказавшегося похожим на огромное болото, заросшее тростником, Пржевальский оставил большую часть багажа, а сам отправился с верблюдами к новооткрытому хребту Алтынтаг — охотиться на их диких сородичей: о них европейцы только слышали.

За 40 дней в предгорьях Алтынтага было пройдено 500 вёрст. В пути встретился лишь один дикий верблюд, подстрелить которого не удалось. Эти животные оказались более чуткими и подвижными, чем их одомашненные собратья.

Однако были сделаны астрономические измерения и съёмки до сего времени неизвестного района. Вскоре казаки добыли три шкуры диких верблюдов: основная часть экспедиции в это время находилась на Лобноре. Пржевальский же продолжал съёмку озера. Его внимание привлекли несметные стаи перелётных птиц, собирающиеся на Лобноре.