В том, что отдельной строкой задания было предписано «проведывать о пряных зельях», ничего удивительного нет — на торговле перцем и другими «пахучими и жгучими травами» зарабатывались огромные деньги. Других способов консервирования мяса и рыбы, кроме засолки, вяления и копчения, не было известно: солонина из бочек, бывшая основным мясным продуктом большинства европейцев, часто «попахивала» и вкус ее так приедался, что, не сдобренная перцем или иными приправами, она просто не лезла в глотку. Потому, хоть и дороги были пряности, покупать их все равно приходилось. Охота за перцем была если не основной, то одной из главных причин для разведывания морских путей на Восток.

Для того чтобы Кожин, занятый разведкой и другими своими хлопотными делами, связанными с выполнением задания, не дал маху в торговых делах, ему было велено взять с собой двух купцов «не стары годами». Еще в экспедицию включили двоих навигаторов для съемок местности, были также приданы два инженер. Кроме того, прикомандировывались 100 драгун — им следовало, придя к плотине, встать там лагерем и ждать трудников, коих должны были прислать следом. Драгунам указывалось охранять их, покуда те копали бы канал или прорывали плотину. Всем офицерам было накрепко велено не обижать местное население.

4 марта Черкасский прибыл в Петербург, явил Высочайший указ Сенату и изложил свои требования из тринадцати пунктов. Сенат их заслушал 14 марта, определил, откуда брать войска, сколько требуется отпустить жалованья и припасов отряду, как переправить все это на восточный берег Каспия, сколько дать товаров для Кожина, откуда брать артиллеристов, лекарей, инженеров и прочих специалистов, потребных Черкасскому. Посольскому приказу было поручено изготовить «кредитные грамоты» для хивинского и бухарского ханов, а также для индийского Великого Могола. Самому Черкасскому решено было выдать «на полковые и другие расходы тысячу рублей», дать подводы и суда с гребцами, чтобы из Нижнего Новгорода он мог добраться до Астрахани. Судя по всему, князь был наделен исключительными полномочиями, поскольку все его требования, вплоть до мелочей, всеми исполнялись в полном объеме и без малейшего промедления. Все выходило «не по-русски» стремительно.

Из Петербурга князь выехал в Москву, а оттуда почти сразу же в Казань и далее в Астрахань, где посланный ранее поручик Кожин уже готовил суда для перевозки войск морем. Вскоре после приезда Черкасского в Астрахань стали подтягиваться войска, назначенные к сформированию экспедиционного отряда: полки регулярного войска, драгуны Астраханского полка, яицкие и гребенские казаки, драгунский эскадрон, сформированный из пленных шведов, изъявивших желание участвовать в походе, под командой майора Франкенберга, уроженца Силезии; шведы славились дисциплиной и боевой выучкой, они отлично проявили себя в схватках с ногайцами и другими степными народами. Кроме того, Черкасский пригласил к участию в походе астраханских дворян, среди которых главным был, конечно же, князь Михаил Самонов; к отряду также были прикомандированы чиновники, провиант-мейстер Акинфов и прочие служители, которых набралось до пятидесяти человек. Всего в отряд вошло 6655 человек. Он был в изобилии снабжен всем необходимым, отменно вооружен и экипирован для похода. Офицеры экспедиции были люди все сплошь ученые и, что называется, «видавшие виды»: повоевавшие и побродившие по свету на своем веку.

Поручику Кожину выданы были товары на 5000 рублей, а также на провоз товара 1000 рублей. Провиант отряду дали из расчета на год. Припасы и имущество решено было свозить в Астрахань, ставшую сборным пунктом экспедиции, а оттуда уже отправить, куда укажет командующий походом Бекович. Он сам выехал в Казань, где принял Пензенский полк, из Воронежа пришел Крутоярский полк, от Астрахани в поход шел Риддеров полк.

Лето 1716 года ушло на сборы и подготовку, так что управились со всеми делами только к сентябрю. Перед походом Черкасский приказал всем выдать жалованье за год вперед: офицеры получили полное армейское содержание, а нижним чинам выплатили из расчета по пятнадцати алтын в месяц. Казакам, шедшим в поход, причиталось: атаманам по сорок рублей, полковникам по двадцать пять рублей, есаулам, хорунжим и писарям по пятнадцать, а простым конникам по десять рублей.

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

К 9 октября флотилия достигла мыса Тюк-Караган, где к экспедиции присоединился Ходжа Нефес. Здесь была заложена первая крепость, названная Петровской в честь Святого Петра, — впредь отсюда должны были посылаться гонцы в Астрахань с известиями о ходе экспедиции. Для возведения укреплений и несения гарнизонной службы оставили Пензенский полк под командой полковника Хрущева. Место для постройки крепости выбрали неудачно: рядом не было пресной воды, а в вырытых колодцах вода становилась соленой уже через сутки. Отсюда в Астрабад, к тамошнему хану, были направлены поручики Кожин и Давыдов, назначенный послом в Бухару. Планировалось, что Давыдов и члены посольства получат пропуск от астрабадского хана через его владения в Бухару.

Пока Кожин и Давыдов ходили к Астрабаду, Бекович приказал отряду двигаться дальше на юг; пройдя 120 верст, караван судов встал на якоря у залива Бехтир-лиман. Здесь тоже заложили укрепление, названное Александровским, в месте очень удобном для обороны и оставили три роты из Риддерова полка под командой майора.

К 5 ноября флотилия добралась до Красноводской косы, где, как считал Бекович, располагалось старое русло Амударьи. Сюда же прибыл Кожин с сообщением, что астрабадский хан отказал в пропуске поручика Давыдова через персидские владения. Тогда Черкасский отправил в Астрабад князя Самонова. Тем временем полным ходом шло сооружение еще одной — Красноводской — крепости, место для которой тоже выбрали неудачное — от стоячей соленой воды шло испарение, делавшее местность нездоровой, к тому же ощущалась нехватка пресной воды, и не было поблизости ни травы, ни леса. Окончание строительства и защита этого укрепления были поручены фон дер Вейдену, а сам Бекович с Астраханским и Азовским полками, частью артиллеристов и морской командой, снятой с судов, решил возвращаться в Астрахань сухим путем — плыть по морю было слишком опасно из-за льда.

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