По Высочайшему повелению летом 1836 г. в Астрахани и Оренбурге задержали более 500 хивинских купцов и товаров при них на миллиона полтора. Хивинцы взмолились и хан Аллакул выслал на первый раз 26 пленников, все они оказались старыми людьми, прожившими в плену по 30–40 лет, а один старик прожил 55 лет. За них вернули только пять торговцев. В следующем году хивинцы прислали еще 5, потом сразу 80, они прослышали о постройке в степи новых укреплений и приготовлениях к походу. Действительно, в это время уже состоялось Высочайшее распоряжение «О воинском поиске в Хиву, дабы принудить хана силой оружия выдать всех русский и доставить нашей караванной торговле полную свободу». После уже дознались, отчего хан так упорствовал: англичане обнадежили его помощью на тот случай, если Россия объявит войну.
Почти два года прошли в приготовлении к новому походу. За это время в степи выстроили два укрепления: одно на реке Эмбе, за 500 верст от Оренбурга, другое под названием Ак-Булак (Пять Ключей) за 175 верст дальше; их снабдили продовольствием и фуражом. Такие же запасы были доставлены в приморское укрепление Александровское, все это назначалось для отряда по пути его следования в Хиву. Однако предстоящий путь был мало известен. Почти перед самым походом инженер, который строил укрепления, вернувшись докладывал, что местность от Эмбы до Ак-Булака низменная, солончаковая, почва самая бедная и безводная. Как после оказалось и места для укрепления тоже выбрали неудачно: возле Эмбинского поста подножные корма были плохи, а в укреплении Ак-Булак вода для питья негодная. Дальнейший путь до Аму знали только по рассказам пленных: там предстояло подняться на Усть-Урт. Это плоская возвышенность до 100 саженей над уровнем моря, которая круто обрывается своими берегами, известными под названием «чинка».
Пехота Оренбургских линейных батальонов в зимней походной одежде
Перовский раньше так и наметил свой путь через Усть-Урт к берегу Аральского озера, оттуда чинком Усть-Урта на хивинский город Куня-Ургенч, всего 1320 верст.
Изменить намеченный путь уже было поздно, укрепления построены, сделано распоряжение о доставке в Ак-Булак припасов. Перовский рассчитывал там выждать, пока Усть-Урт покроется снегом и будет сделана разведка для подъема. Войск собрали больше, чем в экспедицию Бековича, а именно 3½ батальона пехоты, 2 полка уральских и 3 сотни оренбургских казаков, всего около 5 тысяч, кроме того, 22 орудия. Солдаты одеты по зимнему, каждому дали киргизский полушубок, куртку из молодых овчинок, теплую шапку и широкие длинные сапоги. Для подстилки, вместо постелей, заготовили войлоки, а чтобы было где укрываться от стужи – джу-ламейки или круглые войлочные палатки. Так как отряд поднимал с собой, кроме всего этого, боевые припасы, сено, овес и шестимесячный запас продовольствия, то согнали со степи более 12 тысяч верблюдов. Вьючили по 14 пудов на каждого: 7 пудов на одной стороне, 7 пудов на другой; два таких вьюка прикрепляли к верблюжьему седлу, после чего их покрывали войлоком. В тяжелые орудия, в арбы для больных и в бударки (крытые повозки) также впрягали верблюдов. Таким образом снаряжался огромный караван, тяжелый на подъем, грузный по ходу, это-то его и погубило.
14 ноября 1839 г. на городской площади Оренбурга собралось войско, выступавшее в поход. После молебна прочитали приказ Перовского:
«Товарищи! Нас ожидают стужа и бураны и все трудности дальнего степного и зимнего похода. Войска Оренбургского корпуса в первый раз выступают в значительном составе против неприятеля; Россия в первый раз карает Хиву, эту дерзкую и вероломную соседку. Через два месяца, даст Бог, будем в Хиве и в первый раз еще в столице Ханства перед крестом и евангелием русские будут приносить теплые молитвы за Царя и Отечество!