В состав экспедиционного отряда вошли казаки из Оренбургского и Уральского войск, Первый Оренбургский полк — всего около 4 тыс. чел. Артиллерийское вооружение отряда было весьма основательным: 22 пушки и четыре станка для пуска ракет. Несколько тысяч верблюдов должны были перевозить грузы.
14 (26) ноября 1839 г. передовые экспедиционные подразделения покинули Оренбург. Лишь к концу месяца отряд преодолел 150 верст и добрался до крепости на р. Илек. Ударили сильные морозы, до — 30° и ниже. Стал ощущаться сильный недостаток в топливе. С приближением к опорному пункту на р. Эмба выпал глубокий снег.
Несмотря на основательную подготовку, идея зимнего похода оказалась неудачной. Морозы, снега, гололед, закрывающий панцирем траву, оказались страшнее летнего зноя.
В конце декабря в одном из писем к Паскевичу император писал: «Экспедиция наша в Хиву делает много шуму, но она необходима, и шум этот нас пугать не должен. Покуда известие от Перовского только за небольшим 300 верст от границы. Мороз был до 32°; но все шло хорошо, и обмороженных вовсе не было; но не один холод, много еще препятствий следует преодолеть до решительного успеха».
Здоровье людей было еще в довольно удовлетворительном состоянии; но пятая часть верблюдов не могла продолжать путь. В становище на Эмбе пришлось дать отряду отдых на несколько дней. А в Хиве уже получили известия о движении русских и выслали навстречу свою конницу.
Отряд хивинцев, численностью до 3 тыс. человек, произвел нападение на становище у Ак-Булака, где находилось около 400 русских солдат (из них половина больные). Это нападение было отбито после упорного боя. У нас выбыло из строя около 20 человек. На следуюшую ночь хивинцы атаковали передовую группу из отряда Перовского, направившуюся к Ак-Булакскому укреплению, чтобы перевезти оттуда припасы к реке Аты-Якши. Солдаты выстроили вагенбург, часть из них зашла хивинцам во фланг — и степные воины опять потерпели неудачу.
Примерно в это время отряд Перовского выступил из Эмбинского укрепления по направлению к Аты-Якши. Впереди отряд ожидали глубокие снега, бураны при двадцатиградусном морозе, отсутствие топлива. Резко выросли санитарные потери.
За две недели отряд преодолел около 600 верст. По достижении укрепления на р. Ак-Булак, в строю оставалось всего 1900 человек; годными для дальнейшего пути было только 2,5 тысяч верблюдов.
В этих обстоятельствах 4 февраля 1840 г. Перовский принял решение возвращаться обратно. На Эмбе отряд задержался на 3 месяца и лишь 2 июня вернулся в Оренбург, везя с собой 1200 больных. При незначительных боевых потерях было потеряно свыше 1000 чел., умершими от болезней и пропавшими без вести.