Во второй половине сентября 1716 года экспедиция снова двинулась к восточному побережью Каспия. Теперь это была целая армия из 70 судов, на которых разместились более 5 тыс. человек — 3 пехотных и 2 казачьих полка, 500 пензенских и 100 астраханских драгун, артиллеристы, инженеры и строители, а также купцы, подьячие, переводчики, лекари…

К этому времени затраты на восточный поход уже составили порядка 220 тыс. руб. — сумму баснословную, да еще при пустой казне! Это лишний раз доказывает, какое значение придавал Петр осуществлению своей идеи прорубить «окно в Индию». 9 октября суда причалили у знакомого берега в заливе Тюб-Караган, где их встретил Ходжа Нефес с небольшой свитой. Здесь Бекович оставил пехотный полк полковника Хрущева, поручив тому строить крепость, хотя в инструкциях Петра такой пункт отсутствовал. Надо полагать, именно по этой причине между Бековичем и Кожиным, который держался подчеркнуто независимо, произошла первая крупная размолвка. Кожин доказывал, что местность тут пустынная, вода в колодцах гнилая, следствием чего станут болезни в гарнизоне. Но Бекович настоял на своем, указав, что именно отсюда начинается старая дорога на Хиву.

По этой дороге князь направил в Хиву послов с грамотами и подарками. К хану Шергози поехал дворянин Воронин. Другому дворянину — Алексею Святому — поручалось обхаживать родственника хана, влиятельного вельможу Колумбая.

1716 год, марта 31. Именной указ Петра I поручику А. И. Кожину.

Одновременно другое посольство во главе с дворянином Давыдовым было направлено к бухарскому хану. Но добираться до Бухары Давыдову предстояло через Персию. Доставить его морем в персидский город Астрабад (Горган) Бекович поручил Кожину. Затем основные силы экспедиции двинулись к заливу Красные Ворота, где также была заложена крепость на месте будущего города Красноводска.

Через некоторое время сюда прибыл Кожин, а с ним Давыдов, так и не попавший в Бухару. Оба объяснили, что иранские власти не пропустили посольство через свою территорию.

Не поверив Кожину, Бекович тайно направил в Астрабад князя Самонова — крещеного персиянина, получившего свой титул на русской службе.

Тем временем Кожин развил бурную деятельность. Осмотрев местность и проведя ряд топографических съемок, он уверенно заявил, что никакого старого русла здесь нет, что вода самотеком тут не пойдет и потому строить крепость не имеет смысла. Кроме того, «купчины» Кожина собрали тревожные сведения. Никто в степи не верил, что русские пришли с миром. Враждовавшие между собой Хива и Бухара якобы договорились воевать вместе против чужаков и уже готовились к боевым действиям.

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

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

Между Бековичем и Кожиным произошел очередной крупный разговор. Бекович, как глава экспедиции, потребовал безоговорочно выполнять все его указания. Закончилось тем, что Кожин самовольно отправился в Петербург, намереваясь убедить Петра и Меншикова в целесообразности отмены похода.

1716 год, мая 18. Выпись в Сенате о грамотах русских царей к падишахам Индии.

(л. 42 об.) Такова грамота написана к слушанию, чтена в Сенате майя в 7-м да в 10-м числех и притом докладывано о подчерченых словах. А имянно.

1. В грамоте 183-го году, которая вся списана сего титла (государь Иверские (л. 43) земли, карталинских и грузинских царей, и Кабардинские земли черкаских и горских князей) не писано. А в других писано ль, сего в ведомости, с Москвы присланной, не написано.

2. Во 159 году в грамоте от ц. в. к индейскому шаху в титле писано брату нашему, великому государю. А во 183 году — велеможнейшему брату нашему, великому государю. А в 203 году в проезжей написано в титле шахове против грамоты 159 году — брату нашему, великому государю, а велеможнейшаго не писано, и ныне в титле шахове велеможнейшаго писать ли?

3. В прежних грамотах писано к шахом индейскому и персицкому — братом. А во 194 году по имялному царского величества указу персицкого шаха братом писать не велено и не пишется.

4. Оимяни, понеже подлинной ведомости не имеетца, того для порозжее место оставлено на разсуждение как написать, так ли как в печатной немецкой книге 171.1 написано, или по скаске в Москве индейцов, или оставить так и за отворчатою печатью послать, и тамо, уведомясь, велеть вписать.

5. Наше царского величества любительное поздравление ни в которой грамоте (л. 43 об.) к индейскому шаху не писано. А к персицкому шаху и к салтану турецкому пишется.

6. В прежних грамотах писано, чтоб товары купчине продавать и покупать беспошлинно. И сие ныне писать ли?

И 1716 майя в 10 день. По указу великого государя Правительствующий Сенат, слушав той грамоты, приговорили против того грамоту к шаху индейскому написать и послать. Ив титле царского величества государь Иверские земли, карталинских и грузинских царей, и Кабардинские земли черкаских и горских князей написать, ибо того к одному только персицкому шаху писать не велено. А в шахове титле велеможнейшему писать. А братом, понеже к персицкому шаху по имянному царского величества указу писать не велено, (л. 44) то и к нему не писать. Имя написать то, которое в печатной немецкой книге, имянуемой лексикон, напечатаной в Лейпциге в 1711 году Шауалем, царского величества любительное поздравление писать. О том, что товары продавать и покупать безпошлинно, написать против прежняго обыкновения. Что ж в титле шахове напредь сего писывано всеа восточныя страны повелителю, и то отменить, а написать кроме слова всеа просто восточныя страны повелителю.

Надо сказать, что и Бекович понимал всю сложность своей миссии. В Астрахани он получил весточку от своих послов, отправленных в Хиву. Воронина приняли дурно. Хан Шергози находился в походе, и русского посла содержали фактически под арестом. Лишь благодаря Колумбаю, получившему подарки от Святого, удалось добиться для Воронина некоторого послабления. В марте 1717 года вернулся из похода хан Шергози. Он принял послов, выслушал их, но продолжал удерживать в Хиве, не давая никакого ответа. В городе, писал Воронин, заметны явные признаки военных приготовлений.

Итак, надежды привлечь хана на свою сторону не оправдались, но Бекович полагал, что Шергози станет сговорчивее, когда увидит мощь русского войска.

В Астрахани Бекович собрал дополнительные силы, к которым присоединились татарские, армянские и русские купцы.

Между тем численность основного контингента неуклонно снижалась. В новых крепостях, как и предсказывал Кожин, начались болезни. К маю 1717 года в каждом из двух гарнизонов умерло по 500 человек.