Первую крепость князь заложил на мысе Тюп-Караган, на той самой безжизненной песчаной косе у моря, где всякое строительство было бессмысленно: вокруг не было воды, а в колодцах, которые он приказал рыть, вода была сильно подсолена да к тому же в два дня протухала. Протесты его офицеров Кожина и фон дер Виндена ни к чему не привели. В недостроенной крепости посадил он Казанский полк с одиннадцатью орудиями, а сам направился в Красные Воды. Перед отплытием с Тюп-Карагана Бекович по старой караванной дороге отправил в Хиву послов – Ивана Воронина и Алексея Святого – с объявлением о мирных целях посольства и с подарками.

В Красноводском заливе, хорошо обжитом туркменами, Бекович тоже не стал утруждать себя подысканием сколько-нибудь подходящего места для укрепления, боясь, возможно, потревожить туркмен, и заложил у самого моря крепость, в точности подобную тюп-караганской, условия в которой были разве что «еще злее»; так, еще до начала похода большая часть войск экспедиции совершенно бесполезно для дела оставлена была умирать в безводных и зловонных прибрежных укреплениях. Так как время было уже зимнее, возле заложенных крепостей оставил Бекович и корабли, а сам с половиною войска вернулся в Астрахань. Тут стали происходить с ним вещи все более странные.

Готовясь к решительному выступлению на Хиву весной 1717 года, капитан лейб-гвардии Преображенского полка Александр Бекович-Черкасский первым делом обрил голову, облачился в восточную одежду и принял имя, которое носил до крещения, – Девлет-Гирей («Покоритель царств»). Тогда же были вызваны им из Кабарды братья, Сиюнча и Ак-Мурза, со своими нукерами. Разумеется, и прибытие этих странных гостей и, в особенности, престранная метаморфоза, происшедшая с самим главнокомандующим, повергли в полное недоумение офицеров отряда.