И вот весной 1873 года отряды общей численностью около пятнадцати тысяч человек выступили в поход. Главнокомандующий фон Кауфман возглавлял Туркестанский отряд, который выступал двумя эшелонами: из Туркестана и из Казалинска. Командование Оренбургским отрядом было возложено генерал-губернатором Крыжановским на генерал-лейтенанта Веревкина. Мангышлакский отряд возглавлял полковник Ломакин, а Красноводский отряд вновь возглавил полковник Маркозов. Однако хан Хивы, зная те огромные расстояния, которые придется преодолеть наступающим, и те трудности, с которыми им придется столкнуться, поначалу чувствовал себя в безопасности. Тем не менее все отряды на этот раз неуклонно приближались к Хиве, и хан в конце концов заволновался. Пытаясь умилостивить противника, он освободил всех русских рабов и пленников, удерживаемых в Хиве, — двадцать одного человека, — но этим шагом уже ничего не добился.
В конце концов до границ ханства не дошла только часть Красноводского отряда, двинувшаяся к Хиве прямиком, та же часть, что отправилась через Мангышлак, вскоре присоединилась к Оренбургскому отряду и оказалась даже в авангарде движения. Казалинский отряд в свою очередь присоединился к Туркестанскому, и к концу мая, успешно преодолев все трудности похода, русские войска подошли к Хиве с двух направлений. Причем весьма замечателен тот факт, что Оренбургский отряд, которому надлежало преодолеть наибольшее расстояние (около полутора тысяч километров) достиг цели на два перехода ранее Туркестанского. Хотя поначалу глубокие снега, достигавшие порой двадцати градусов морозы, бураны и разбитая обозами дорога, представлявшая цепь ухабов, казалось, вновь объединились, чтобы выручить Хиву из беды. Однако на этот раз Оренбургский отряд прибыл к концу марта на Эмбенский пост только с сорока пятью больными. Сами войска, правда, сознавали, что успешным движением обязаны усердию и заботливости киргизов, которые выставляли на всяком ночлеге даже больше кибиток, чем было назначено, сена накладывали на пол достаточно, а сверху застилали кошмами. И к тому же отказались от платы.
Мало того, в особенно холодные или бурные ночи киргизы размещали эшелон по аулам или в собственных землянках. Волостные и аульные старшины постоянно шли с отрядами и транспортами и, когда сани с тяжестями останавливались в сугробах, от изнурения лошадей и верблюдов, припрягали к ним своих, также не соглашаясь брать за это никакого вознаграждения. Такое поведение людей, еще недавно бунтовавших, свидетельствует о радикальной перемене их отношения к России и должно быть поставлено в заслугу деятелям народного управления.