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

От царя Бекович вышел в чине гвардейского капитана.

Во второй половине сентября 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 об.) к индейскому шаху не писано. А к персицкому шаху и к салтану турецкому пишется.