Многие выражали желание сопровождать Пржевальского. Николай Михайлович долго колебался в выборе. Наконец он выбрал восемнадцатилетнего юношу Эклона — сына одного из служащих Музея Академии наук и молодого прапорщика Повало-Швыйковского.
В состав казачьего конвоя экспедиции Пржевальский просил включить Чебаева и Иринчинова, сопровождавших его в первом путешествии.
Искать помощников и готовиться к экспедиции Николай Михайлович начал еще задолго до официального решения правительства. Он заготавливал походные сумки, патронташи, одежду для себя и для всего отряда, искал хороших собак.
В начале марта 1876 года он писал Пыльцову из Петербурга: «Теперь я одной ногой уже в Тибете, и если эта экспедиция будет идти так же счастливо, как первая, то мне будет принадлежать честь исследования всех самых неведомых стран Центральной Азии. Поприще завидное, хотя и трудное».
Распоряжением правительства от 15 марта подполковник Пржевальский, прапорщик Повало-Швыйковский, вольноопределяющийся Эклон и семь казаков командировались на два года в Центральную Азию.
Перед отъездом в экспедицию Пржевальский вместе с двумя своими помощниками провел две недели в «Отрадном». Здесь он охотился и обучал будущих спутников стрельбе из штуцеров и револьверов.
23 мая Николай Михайлович простился с матерью и няней Макарьевной. 6 июня он и его спутники прибыли в Пермь. 13 июня со всем снаряжением экспедиции они выехали из Перми на 13 почтовых лошадях. Хлопотно и накладно было везти громадный багаж по скверной уральской дороге, — повозки часто ломались и приходилось платить за их починку.
За Уралом раскинулись необозримые степи. Чем ближе к Семипалатинску, тем степь становилась все более суровой и пустынной и все более напоминала Гоби.
3 июля в Семипалатинске произошла радостная встреча Пржевальского со старыми товарищами — казаками Чебаевым и Иринчиновым.
Отсюда экспедиция выехала на пяти тройках. В Верном (ныне Алма-Ата) Николай Михайлович взял еще трех казаков, а в Кульдже нанял переводчика — Абдула Юсупова, знавшего тюркский и китайский языки.