Наконец Николай Михайлович остановил свой выбор на 18-летнем Федоре Леонтьевиче Эклоне, сыне одного из служащих Академии наук. Он пригласил юношу на лето 1875 г. в «Отрадное» и обучал всему, что может понадобиться в экспедиции. В октябре Эклон выдержал экзамен и поступил в Самогинский полк.

Вторым помощником Пржевальский решил взять сына соседки по имению прапорщика Звенигородского полка Евграфа Повало-Швыйковского, которого знал с самого детства. Правда, этот юноша не был охотником и не имел нужных познаний, но Пржевальский надеялся, что он быстро всему научится. Взял он его, собственно, за хороший характер, крепкое здоровье и личную преданность.

Спутники Пржевальского по монгольскому путешествию — забайкальские казаки Иринчинов и Чебаев — прислали письмо с просьбой взять их с собой снова. Таким образом, основной состав экспедиции был определен.

14 января 1876 г. Пржевальский представил в Географическое общество заявку на новое путешествие с расчетом его стоимости. 31 января Совет Общества единодушно одобрил предложение Николая Михайловича и поручил вице-председателю Общества П. П. Семенову выхлопотать у государственного казначейства необходимые для экспедиции 24 740 руб.

Первые месяцы 1876 г. Пржевальский провел в Петербурге, заканчивая рукопись и вместе с Эклоном и Повало-Швыйковским снаряжаясь в экспедицию. В конце апреля работа над вторым томом «Монголии и страны тангутов» была окончена, и Николай Михайлович смог выбраться в деревню попрощаться с родными.

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

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

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

В горы Восточного Тянь-Шаня экспедиция направилась сначала по широкой, густо заселенной долине реки Или, а затем вверх по Кунгесу правому истоку Или. Уже в лесах нижнего Кунгеса встретилось довольно много зверей. Удалось добыть темно-бурого тянь-шаньского медведя, отличающегося длинными белыми когтями на передних лапах. Поразило путешественников в лесах Кунгеса обилие диких фруктовых деревьев — яблонь и абрикосов.

Из долины Кунгеса поднялись в долину реки Цанма, по берегам которой уже тянулись еловые леса. Перевалив через хребет Нарат, экспедиция вышла на плато Юлдус. Это плато, а точнее, межгорная обширная котловина обетованная страна для скотоводов. Здесь всюду превосходные пастбища, к тому же нет мошек и комаров. На Юлдусе путешественники провели около трех недель, занимаясь преимущественно охотой.

Ко времени прихода на Юлдус Пржевальский окончательно убедился в полной непригодности одного из помощников к путешествию. Повало-Швыйковский так и не научился ни стрелять, ни делать чучела, ни вести съемку местности. Пришлось отослать его обратно. Пржевальский опять остался с одним помощником, к счастью, энергичным и усердным.

Преодолев южные отроги Тянь-Шаня, экспедиция вступила в Восточный Туркестан, на земли недавно возникшего мусульманского государства, возглавляемого ханом Якуб-беком. Восточный Туркестан, или Кашгария, представляет собой равнину. Большая часть ее занята пустыней Такла-Макан, окаймленной горными системами Тянь-Шаня, Памира, Куньлуня. Это, собственно, огромная котловина на высоте от 780 м (на востоке) до 1500 м (на западе).

Кашгарский хан Якуб-бек вопреки заверениям в гостеприимстве, крайне настороженно встретил экспедицию. Путешественникам было разрешено остановиться в окрестностях города Курля (Корла), причем караул не подпускал к ним никого из местных жителей.

Через две недели было получено разрешение двигаться дальше. 4 ноября экспедиция выступила из г. Курля к Тариму и Лобнору. Путешественников сопровождал конвой под командой Заман-бека, бывшего русского подданного. Конвой сильно осложнял работу, не давал возможности общаться с местным населением. Надеясь заставить русских отказаться от дальнейшего путешествия, конвой вел караван к реке Тарим самым трудным путем, с переправами вплавь в мороз через реки Кончедарья и Инчикедарья.

Преодолев от Курли около 90 км, экспедиция вышла к Тариму в месте впадения в него Угендарьи. Пройдя 200 км вниз по Тариму, путешественники 9 декабря переправились через реку на плоту. От переправы Айрылган до Лобнора было уже недалеко. Однако конвойные обманули Пржевальского, сказав ему, что прямого пути на Лобнор нет, и уговорили пойти на юг, в деревню Чархалык (Чарклык), где удобно зимовать.

Оставив в Чархалыке караван с собранными материалами, трех казаков и конвой, Пржевальский с остальными тремя казаками и Эклоном выехал 26 декабря к лежавшим поблизости горам Алтынтаг.