Казанский губернатор Салтыков и астраханский воевода Чириков получили от царя распоряжение о безусловном выполнении всех требований Бековича.
Рядом с Бековичем неотлучно находился Ходжа Нефес. Они беседовали часами, и туркмен подробно отвечал на все вопросы князя.
Лето и значительную часть осени Бекович провёл в Казани и Астрахани, отдавая все свое время подготовке экспедиции.
1716 года, февраля 14. Письмо канцлера Г. И. Головкина секретарю Посольской канцелярии П. В. Курбатову.
Копия с письма, отправленного к господину секретарю Курбатову.
Господин секретарь. Понеже его царское величество изволил определить князь Александру Бековичю-Черкаскому ехать послом к хивинскому хану, а к бухарскому хану и к моголу индейскому послать купчин, того ради писал я в Сенат, с которого при сем прилагается список, чтоб они тебе приказали написать верущие грамоты к ним и, высмотря, велели запечатать. И для того посылаю с титулов, каковы писываны к ханом хивинскому и бухарскому, списки, против того можешь написать верющие, и черные сначалу прочитать им. А потом когда прикажут набело написать, справясь и осведомясь имянно о ханских имянах, кто ныне хивинским и бухарским, а о титуле могола индейского можешь справиться в Посольском приказе, и о том писать к Москве к секретарям, ибо изволил его царское величество сказывать, что от князь Петра Ивановича Прозоровского посылан был туда купчина, и чаять, что с ним грамота послана была. А купчины имяна напишешь в грамоте, о которых объявит он, князь Александр Бекович, от которого о его посылке будешь сведом, и по тому те грамоты и напишешь. А каковы оныя написаны будут, о том ко мне пиши и пришли с оных списки. И ежели что еще повелит Сенат вам исправить ко отпуску его, князь Александра Бековича, то с воли их чинить. А в грамоте верющей к хивинскому хану надлежит приписать и об отпуске с ним хивинского посла, которой удержан в Астрахани. Тако жио той материи, о которой с ним, послом, писано было в грамоте, надлежит в ту верющую внести, понеже у хивинского посла прежнюю грамоту велено отобрать.
Получено в 4-й день марта.
Наконец, 7 ноября экспедиция — около двух тысяч солдат, офицеров и специалистов — направилась на двух шхунах и 27 стругах к Гурьеву. Но разыгравшаяся буря заставила флотилию вернуться в Астрахань. Зимнее время Бекович использовал для постройки 20 новых судов, более надежных и быстроходных.
Поздней весной — 25 апреля 1715 года — экспедиция отплыла из Астрахани и благополучно достигла Гурьева. Здесь к Бековичу привели кочевников-туркмен, которых он долго и подробно расспрашивал о старом русле. Кочевники подтвердили сведения, полученные князем ранее от Ходжи Нефеса, добавив, что для поворота реки потребуется прорыть канал длиной 20 верст к заливу Красные Ворота.
Из Гурьева доплыли до залива Тюб-Караган на восточном побережье Каспия. Отсюда основные силы экспедиции двинулись берегом моря к заливу Красные Ворота.
Небольшой отряд во главе с дворянами Федоровым и Званым был послан в разведку для осмотра старого русла Амударьи и проверки сведений, полученных от кочевников. Вместе с разведчиками отправился и Ходжа Нефес.