
Начали с морского похода: 15 сентября 1716 года экспедиция князя Черкасского вышла в море на шестидесяти девяти различных судах. Из приведенных ранее служилых людей в Астрахани на зимовку остались драгуны и казаки. При полках и командах состоял полный комплект штаб и обер-офицеров, также шли в поход поручик Кожин, унтерлейтенант Давыдов и штурман Бранд. Судьба этого штурмана весьма любопытна: несмотря на свою «иностранную фамилию», штурман был природный калмык, а Брандом его прозвали потому, что он долгое время служил у голландского купца Бранда, российского резидента в Амстердаме, где и выучился на штурмана. Вернувшись в Россию, был принят на флот и служил весьма усердно. Именно его судьба послужила поводом для бесконечного тиражирования байки о том, как денщик-калмычонок, поехавший с боярским сыном в Голландию, выучился там вместо своего барина и по возвращении в Россию на экзамене так поразил царя Петра, что тот немедленно произвел его в офицеры, а боярского сына-неуча разжаловал в солдаты и отдал в денщики к бывшему его рабу-калмыку.
К 9 октября флотилия достигла мыса Тюк-Караган, где к экспедиции присоединился Ходжа Нефес. Здесь была заложена первая крепость, названная Петровской в честь Святого Петра, – впредь отсюда должны были посылаться гонцы в Астрахань с известиями о ходе экспедиции. Для возведения укреплений и несения гарнизонной службы оставили Пензенский полк под командой полковника Хрущева. Место для постройки крепости выбрали неудачно: рядом не было пресной воды, а в вырытых колодцах вода становилась соленой уже через сутки. Отсюда в Астрабад, к тамошнему хану, были направлены поручики Кожин и Давыдов, назначенный послом в Бухару. Планировалось, что Давыдов и члены посольства получат пропуск от астрабадского хана через его владения в Бухару.
Пока Кожин и Давыдов ходили к Астрабаду, Бекович приказал отряду двигаться дальше на юг; пройдя 120 верст, караван судов встал на якоря у залива Бехтир-лиман. Здесь тоже заложили укрепление, названное Александровским, в месте очень удобном для обороны и оставили три роты из Риддерова полка под командой майора.
К 5 ноября флотилия добралась до Красноводской косы, где, как считал Бекович, располагалось старое русло Амударьи. Сюда же прибыл Кожин с сообщением, что астрабадский хан отказал в пропуске поручика Давыдова через персидские владения. Тогда Черкасский отправил в Астрабад князя Самонова. Тем временем полным ходом шло сооружение еще одной – Красноводской – крепости, место для которой тоже выбрали неудачное – от стоячей соленой воды шло испарение, делавшее местность нездоровой, к тому же ощущалась нехватка пресной воды, и не было поблизости ни травы, ни леса. Окончание строительства и защита этого укрепления были поручены фон дер Вейдену, а сам Бекович с Астраханским и Азовским полками, частью артиллеристов и морской командой, снятой с судов, решил возвращаться в Астрахань сухим путем – плыть по морю было слишком опасно из-за льда.
С побережья Каспия в Хиву были направлены несколько верных людей, которые получили наказ «расположить в свою пользу хивинских сановников», для чего им были даны товары, предназначенные «в подарки». Они должны были уведомить хана, что князь Черкасский собирается ехать в Хиву послом; в то же время им вменялось в обязанность присылать с купеческими караванами донесения о том, что происходит в Хиве и окрестностях – что слышно, что видно, о чем можно догадываться. Сколько таких посланцев было отправлено, точно не известно, до нас дошли сведения лишь о двоих астраханских дворянах – Иване Воронине и Алексее, по прозвищу «Святой», которых отправили к Кулун-баю, визирю и военному министру хана.
В Астрахань шли двумя отрядами. Передовым командовал поручик Кожин, за ним двигался Черкасский с остальными людьми. Они соединились возле Александровского укрепления и пошли на крепость Петровскую, где обнаружилась картина ужасающего мора: многие солдаты и офицеры были больны, а 120 человек уже умерло. Но при исполнении царевых указов в России с такими «мелочами», как потери среди личного состава, никогда особенно не считались, и князь Александр даже не задумался отдать приказ оставить это погибельное места.