В поход отправились: эскадрон шведских драгун, насчитывавший до 600 человек; две роты пехотных солдат, посаженных на коней; артиллеристы – офицеры и нижние чины, при орудиях и припасах к ним; разные военные и флотские служители; отряд добровольцев, состоявший из русских дворян, мурз и ногайских татар, численностью до 500 человек; казаки – 1500 яицких и 500 гребенских. С отрядом шли богатые караваны купцов, рассчитывавших на охрану военных в опасной степи, где испокон веку пошаливали степняки. Купцов – русских, татарских и бухарских – набралось около двух сотен. Весь отряд насчитывал до 3000 человек. Из лиц известных при отряде находились князь Самонов, астраханский дворянин Киритов, майоры Франкенберг и Пальчиков, братья Бековича – Сиюч и Ак-Мурза, а также Ходжа Нефес.
Конница и караваны верблюдов шли до Гурьева сухим путем двенадцать дней, а неделей позже на кораблях, груженных тяжелыми кладями, их догнал князь Александр с отрядом пехоты. Под Гурьевом войско простояло около месяца, отсюда к хану Аюке Черкасский отправил дворянина Мартьянова с просьбой прислать калмыцкую конницу на подмогу. Мстительный хан ответил ему его же словами, произнесенными годом раньше под Астраханью, при разгроме ногайцами его ставки: «Я не имею на то царского приказа», и людей не послал. Впрочем, он отправил в распоряжение князя своего человека Бакшу, а с ним десять калмыков и туркмен-проводников, которые должны были следовать в отряде Бековича в качестве особого посольства к хивинскому хану.
Здесь же, под Гурьевом, произошла первая стычка с каракалпаками, которые напали на казачьих табунщиков и захватили шестьдесят пленных, среди которых оказался и Ходжа Нефес. Вслед каракалпакам была пущена погоня, которую возглавил сам Бекович. После долгого преследования налетчиков настигли, отбили у них табуны и полон, при этом сами взяли нескольких каракалпаков в плен.
Наконец на седьмой неделе после Пасхи, в начале июля, в самый разгар жары, когда, казалось, никакое движение по степи невозможно, отряд выступил от Гурьева и, минуя большую караванную дорогу, направился к реке Эмбе. Дневок не делали, лишь останавливались на ночлег у степных речек и до Эмбы добрались за восемь дней, совершая усиленные марши по тридцать семь верст в сутки, таким образом проделав около трехсот верст. Эмбу форсировали частью на плотах, частью вброд, затратив на переправу отряда и грузов два дня, а потом снова пошли быстрым маршем и через два дня достигли урочища Богачать, к которому выходила большая хивинская дорога. Отсюда пошли от колодца к колодцу: на Дучкан, Мансулмас и Чилдан. В степных колодцах воды на большое количество людей и животных не хватало, и, придя на место, в первую очередь сами рыли сотню и более колодцев в рост человека.
Возле колодца Чилдан туркменский проводник, караван-баши Мангалай-Кашка, вместе со своими товарищами ночью ушел из лагеря. В степи беглецы разделились – Мангалай-Кашка и шестеро туркмен пошли в улусы калмыцкого князя Даржи, подданными которого они были, а ханские калмыки Аюки – Бакша и с ним еще четверо – отправились в Хиву, далеко обойдя степью заставы и русский лагерь.
От этого места караван-баши стал Ходжа Нефес, который повел отряд на колодцы Сан, Косешгозе, Белявили, Дурали и Ялгысу. Так отряд Черкасского достиг Устюркской возвышенности, тогда называвшейся Иркендскими горами. По гористой местности караван и войска прошли восемьсот верст и, когда до границ владений хивинского хана оставалось восемь дней пути, стали лагерем. Здесь Черкасский собрал совет из офицеров, командовавших подразделениями, и на этом совете решено было пойти на хитрость.