Сенат сделал все нужные распоряжения для отправления экспедиции, и осенью 1716 года Черкасский выехал в Каспийское море из устьев Волги и пристал к урочищу Тюк-Караган, где велел строить крепость в месте, по показанию Кожина чрезвычайно неудобном: не было тут ни земли, ни леса, ни воды свежей, только один песок, нанесенный морем. От Тюк-Карагана Черкасский поехал далее морем и в начале ноября пристал к урочищу Красные Воды, где велел строить другую крепость, также, по отзывам Кожина, на дурном месте, не имеющем ни леса, ни воды, ни травы, при глухом заливе, где морская вода стоячая и гнилая. С Красных Вод Черкасский возвратился к Тюк-Карагану, где в оставленном для строения крепости отряде было больных солдат и матросов с 700 человек да умерло со 120 человек. 20 февраля 1717 года Черкасский возвратился в Астрахань, куда с разных сторон приходили дурные вести; находившийся в русском подданстве калмыцкий хан Аюка писал: «Служилые люди идут в Хиву, и нам слышно, что тамошние бухарцы, кайсаки, каракалпаки, хивинцы сбираются вместе, хотят на служилых людей идти боем; а я слышал, там воды нет и сена нет государевым служилым людям: как бы худо не было?» Посланные Черкасским в Хиву люди также давали знать о неприятельских сборах, боятся, что Черкасский придет не в качестве посла, а возьмет Хиву обманом; посланцам Черкасского говорили: «Для чего вы города строите на чужой земле?» Взявши в Астрахани 600 человек драгун, яицких и гребенских козаков, астраханских дворян, татар, черкес, хивинцев, бухарцев и других народов, тысячи с три человек, Черкасский пошел весною в Хиву сухим путем, и чрез несколько времени разнеслась весть, что он погиб в этом походе со всем отрядом.

В октябре 1717 года яицкий козак татарин Ахметев, бывший в этом отряде, рассказывал, что 15 августа поутру Черкасский пришел к озерам реки Дарьи, дней за шесть пути от Хивы; и в тот самый день и ночью войско сделало себе крепость, обрылось землею, и ров с трех сторон, а с четвертой – озеро. На другой же день утром явилось хивинское войско, конное и пешее, и стало бить из пищалей и пускать стрелы, и в три дня побило козаков человек с десять; Черкасский отбивался из крепости, стреляя из пушек и ружей. На четвертый день хан прислал к Черкасскому с мирными предложениями, и знатные хивинцы целовали коран, что над государевыми войсками зла никакого не сделают и будут соблюдать мирное постановление. После этого Черкасский ездил к хану с подарками. Хан стал ему говорить, что всего русского войска в Хиве прокормить нельзя, надобно расставить его отрядами в пяти городах. Черкасский согласился, и отряд яицких козаков из 240 человек, в котором находился Ахметев, отправился в назначенное ему место в сопровождении тысячи человек конных хивинцев. Отряд ночевал в степи спокойно, но на другой день утром провожатые стали разбирать козаков по рукам и перевязали, оружие, лошадей и пожитки взяли себе; козаков повезли дальше под караулом, но Ахметева отпустили с дороги. Он пришел в Хиву на гостиный двор, где нашел двух яицких козаков, которые рассказали ему, что хан стал сбирать войско после того, как приехали к нему посланники от калмыцкого хана Аюки; накануне прихода Ахметева возвратился в Хиву хан из похода и велел выставить на виселице две головы; хивинцы говорили, что это головы князя Черкасского и бывшего при нем астраханского дворянина князя Михайлы Заманова. Ахметев видел в Хиве и живых русских людей, бывших в войске Черкасского: ходят порознь за караулами, говорить друг с другом не могут. Ахметев уехал из Хивы тайком в караване, отправлявшемся в Астрахань. По рассказу калмыка Бакши, бывшего в походе с русскими, хивинский хан договорился с Черкасским, что последний будет принят в Хиве как обыкновенный посланник; Черкасский с своим отрядом пошел к Хиве, и хан шел с ним вместе, вместе ели и пили; но за день пути до города хивинцы разобрали русских без бою и привели в Хиву. На другой день хан рассказывал Бакше, что он князей Черкасского и Заманова казнил, отсек им головы и, снявши кожу, велел набить травою и поставить у ворот. Бакша видел головы, но не мог признать, действительно ли это головы Черкасского и Заманова, потому что кожа снята и набита травою.

Прошло почти три года. В мае 1720 года приехал в Астрахань хивинский посол Вейс-Мамбеть и прислал список с ханской грамоты к царю. «Прежде, – писал хан, – имели мы с вами дружелюбие, которое и теперь иметь желаем; но между вами и нами произошла ссора от того: пришла к нам ведомость, что едет к нам послом Девлет-Гирей (?);мы обрадовались, но потом услыхали, что Девлет-Гирей между наших улусов хочет строить города; мы ему это запретили, но он не послушался и город построил; потом прислал к нам своего посланца с тем, чтоб чрез большую Дарью-реку мост мостить, что он чрез ту реку будет переправляться с войском, так мы бы прислали к нему лошадей. Мы отправили к нему переговорить обо всем посланника; над этим посланником нашим у Девлет-Гирея ругались, хотели его связать и убить до смерти; посланник ушел и объявил нам, что Девлет-Гирей приехал не для посольства, но для строения города. Мы опять послали к нему еще слуг своих, но он, не допусти их до себя, начал в них стрелять из пушек, произошел бой, и в то время многих наших людей побили, и наши люди многих русских людей побили, и Девлет-Гирея привезли со всякими русскими людьми ко мне, и которые русские люди взяты живые, и тех удержали мы у себя на случай, если вы, великий государь, у нас их спросите, а у нас с вами войну вести и в уме нет». Только в конце августа из коллегии Иностранных дел послан был указ астраханскому губернатору: хивинского посла прислать в Петербург, дав ему подводы и кормовые деньги не как послу, но как арестанту, чем только ему с людьми его можно быть сыту, отправить с ним офицера с пристойным числом солдат, который должен смотреть, чтоб посол как-нибудь не ушел, однако должен обходиться с ним политично и ласково; впрочем, объявить ему, что он отправляется за арестом, потому что его хан поступил неприятельски с князем Черкасским, отправленным в характере посольском.

В начале 1721 года посланника привезли в Петербург. Его привели в Иностранную коллегию и поставили перед министрами. «Какой у тебя словесный приказ от хана?» – спросили его министры; посланник отвечал: «Приказал мне хан донести царскому величеству, что из давних лет между российскими и хивинскими народами бывала любовь и торговля, но по некоторому случаю эта любовь и торговля пресеклись, и потому просит хан, чтоб прежняя любовь установилась и торговля умножилась». «Мы думаем, – сказали министры, – что в целом свете и ни в каком законе нет того, чтоб послов убивать; для чего вы посла царского величества князя Черкасского безвинно убили?» «Правда, что это сделано, – отвечал посланник, – однако он к нам приезжал не как посол, но как неприятель, построил город и в нем оставил с 8000 человек войска; потом к нам приехал и, не доезжая до Хивы за 15 дней, убит нашими войсками на бою, а остальные люди и до сих пор в Хивинской земле, и хан их всех желает отдать». «Хан твой, – говорили министры, – сам прежде присылал к царскому величеству с просьбою построить город для умножения торговли, а потом такому великому монарху сделал такую обиду, посла его невинно убил! Может быть, хан твой на тебя сердит и прислал тебя на жертву, чтоб здесь тебя повесили за князя Черкасского?» «Воля ваша, – отвечал посланник, – только хан прислал меня с объявлением, что желает быть в любви и отдать всех пленных».

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

Говорили, что калмыцкий хан Аюка сносился с Хивою ко вреду России, которой власть он признавал. Казанскому губернатору было много дела с калмыками, этими последними представителями движения среднеазиатских кочевых орд на запад, в европейские пределы. Калмыки запоздали, натолкнулись на сильную Россию и волею-неволею должны были подчиниться ей. Подчиненность была шаткая. Казанский губернатор не раз съезжался в степи с Аюкою-ханом и со всеми его тайшами для постановления условий этой подчиненности. Аюка обещался служить верно великому государю и не откочевывать никуда от реки Волги; в случае неприятельского прихода к Астрахани, Тереку, Казани и Уфе по письму от губернатора посылать своих ратных людей с детьми своими, внучатами и другими тайшами и служить заодно с русскими людьми; не пускать своих калмыков на нагорную сторону Волги и ослушников отсылать в русские города головою. Царицынская линия – ров, охраняемый войсками между Волгой и Доном, – мешала калмыкам переброситься к Крыму и соединиться с татарами против России.