Полковник Гекке выполнил приказ, за лето его отряды построили два укрепления: одно в 500 верстах от Оренбурга, другое на 170 верст далее, в 12 верстах от начала подъема на плато Усть-Урт. Вернувшись в Оренбург и доложив об исполнении приказа, Гекке счел необходимым сообщить в рапорте, что путь «от Эмбы до Чушка-куль состоит из солончаковой низменности и самой бедной, илистой почвы, почти безводной». Но менять что-либо было уже поздно – выступили, рассчитывая на русское «авось» и волю Божью. Слишком много затратили сил и средств, чтобы признать поражение дела, даже его не начав. Идти решили к укреплению на Эмбе, которое планировали достигнуть в первых числах декабря, потом на Чушка-куль. Там устроить большой привал, выслать вперед разведку, чтобы выяснить, много ли снега на плато Усть-Урт. Тем временем к берегу Каспийского моря, до которого от Чушка-куля всего 100 верст, должны были подойти суда, груженные продовольствием и иными припасами для отряда. От пристани их караваном должны были доставить в лагерь раньше прибытия туда основных сил. Убедившись в наличии снега на плато, отряд форсированным маршем должен был идти к Аральскому морю и двигаться вдоль его берега – по уверению беглых рабов, в этих местах пресную воду можно было найти везде.
На берегу Урала построили печи, в которых непрерывно пеклись хлеба, из них потом сушились сухари. Там же сушились картофель, морковь, лук и свекла, тоже для запаса в путь. Обслуживали эти печи солдаты, отобранные из тех, кто хоть чуть понимал в этом деле. Другие же, умевшие держать в руках инструменты, сколачивали ящики, строили лодки, понтонные сани, вьюки для верблюдов, бочки и прочее, чего в степи не сделаешь и взять неоткуда будет. Отдельное внимание было уделено заготовке фуража. Выписали специальную паровую машину для прессовки сена и при ней англичанина-механика.
Одежду пошили специально для отряда, соорудив из «джибуги», валяной шерсти, и толстого сукна полушубки, поверх которых надевались армейские шинели. Изготовили стеганые подштанники, поверх которых надевались шаровары, сапоги были выданы с огромными голенищами: в них помещались войлочные валенки, на ноги к тому же надевались теплые чулки и портянки. К меховому воротнику пристегивалась на крючках черная суконная маска для лица, с прорезями для глаз. Одетые в такую форму солдаты выглядели чудовищно толстыми, неповоротливыми, а маски придавали им и вовсе нечеловеческий вид, словно это было неземное, бесовское войско. При этом солдат должен был нести еще и всю свою амуницию: ружье, боеприпасы, ранец и прочее.
Солдат учили ставить и собирать киргизские юрты, а потом, когда осенью 1839 года пригнали верблюдов, стали учить их, как с верблюдами следует обращаться. Такую подготовку прошли четыре оренбургских линейных батальона, полк уральских казаков, Уфимский казачий полк, а также особые команды саперов и разведчиков. Про Хиву было известно, что город окружен стенами, для их разрушения могли потребоваться пушки. Поэтому в отряд включили казачью конную артиллерию. Кроме того, с собою брали большой «артиллерийский парк» для обслуживания орудий, сигнальные ракеты и фальшфейеры. Обозом везли понтоны и лодки, которые собирались использовать при переправах и на Аральском море. В отряд также вошел сводный дивизион из Уфимского конно-регулярного полка. Этот полк был сформирован по ходатайству Перовского, туда собирали особенно рослых нижних чинов из разных кавалерийских частей.
Весь отряд насчитывал 5 217 человек, при 21 орудии. Всего на одного человека в отряде приходилось по два верблюда, их наняли у киргизов 12450 голов. 18 ноября 1839 года подготовку к походу признали законченной. Отряд разделили на четыре колонны: 1-й колонной командовал генерал Циолковский, 2-й – полковник Кузьминский, 3-й – генерал-лейтенант Толмачов и 4-й – генерал-майор Молоствов.
Четвертая колонна считалась главной, в ней шел сам Перовский со своим штабом. Официально начальником штаба числился подполковник Ивакин, на деле же им руководил штабс-капитан Никифоров, который, состоя при Перовском «для особых поручений» и не имея никаких определенных занятий, распоряжался решительно всем, действуя подчас совершенно самостоятельно, но от имени своего патрона и начальника. Кроме того, со штабом шли чиновники для особых поручений, адъютанты, гвардейские обер-офицеры, прикомандированные к отряду. Еще при штабе отряда была особая группа офицеров, в чью задачу входило геодезическое и этнографическое исследование Хивинского ханства. В главной колонне находились также обоз маркитанта, оренбургского купца Михаила Зайчикова, и так называемый кухонный обоз самого Перовского.
К моменту выступления отряда ни для кого уже не были секретом ни цель похода, ни число войск, ни имена командиров. В степи русских уже ждали.