Гладышев и его люди выступили из Оренбурга 3 сентября 1740 года и более месяца добирались до кочевья Абдулхаира. Не дойдя до него 100 верст, они подверглись нападению разбойничьей шайки из Чиклинского рода киргизов – двумя десятками всадников распоряжались Адиль и Янгилда, племянники главы рода Бабея. Захватив русских, не обращая внимания на крики, что они следуют к их собственному хану, разбойники крепко всех связали, избили и ограбили. Гладышева пырнули ножом в спину. Оказалось, что разбойники охотились именно за поручиком, который когда-то сопровождал к Абдулхаиру полковника Тевкелева. Тогда папаша Адиля и Янгилды, славный батыр Байдара, надумал угнать у русских посланцев табун коней – в степях такие занятия считались почетным делом удальцов. Но караульные, которыми командовал Гладышев, службу несли бдительно, заметили угонщиков, открыли по ним огонь, уложив нескольких киргизов, и лихого Байдару в том числе. Теперь подросшие сыновья пошли по проторенной предками дорожке и этот свой грабеж объявили местью за гибель незабвенного родителя. Чувство горя по погибшему отцу отчасти было заглушено завладением имуществом отряда и уводом в полон яицкого казака Романа Федорова и Петра Максимова, денщика надзирателя Назимова. Разбойники со своей добычей унеслись в степь, а ограбленные и избитые русские посланцы продолжили свой путь, благодаря Бога за то, что ограничилось все только этим. По тогдашним меркам, можно сказать, они весьма дешево отделались!
Прибыв в ханское кочевье, Гладышев и его люди самого Абдулхаира не застали, а потому передали подарки, присланные для хана от казны, его жене ханше Пупайе и старшему сыну Нурали-султану, который специально ждал русских, чтобы сопроводить их к отцу, предусмотрительно державшемуся подальше от кочевья. С Нурали были его дядя Нияз, который прежде ездил с Тевкелевым в Петербург, и шестеро телохранителей хана.
Отдохнув четыре дня в гостях у ханши, отряд Гладышева с Нурали-султаном и Ниязом отправился в степную ставку хана. «Здесь известно, – сказал ему Абдулхаир, – что персидский шах Надир идет на Хиву. Мне же хочется, чтобы город этот был под властью ее императорского величества. Сего ради намерен я ехать в Хиву, и чтобы ты был при мне. Оттуда отправишься навстречу шаху и покажешь ему присланную мне ее величеством грамоту с тем, чтобы шах со мною не ссорился». Гладышев отвечал на это, что коли прислан к нему, то и должен поступать по его ханскому приказу.
Переночевав в ханской ставке, наутро Гладышев и его люди присоединились к ханскому конвою, состоявшему из 3 тысяч нукеров, набранных из киргизов, каракалпаков и аральцев. Снявшись со стоянки, хан выступил на Хиву, добравшись к вечеру до перевоза на реке Улударье, имевшей в этом месте ширину более 150 метров. На берегу были заготовлены двадцать больших лодок для переправы. Возле них и заночевали. Утром начали переправляться, ставя потри-четыре лошади в лодку, а иных пуская вплавь; закончили переправу 4 ноября. К тому времени на хивинский берег прибыла делегация из двух десятков хивинских вельмож во главе со знатным узбеком Авест-Мираном. Хивинские чины слезно просили хана как можно скорее прибыть в город, поскольку им достоверно известно, что шах собирается идти на Хиву. Абдулхаир внял их просьбам и выступил столь поспешно, что русские отстали в степи и долго плутали по ней, прежде чем вышли к городу. Там они узнали, что Абдулхаир уже принял ханство.
Провожатые ввели Гладышева в ханский дворец, где в парадной зале его принял Абдулхаир, сидевший на ханском месте – возвышении, покрытом богатым персидским ковром. На ковре была большая подушка красного бархата, на ней восседал хан, голову которого покрывала чалма из красного шелка. По бокам располагались сорок знатных хивинцев и его степных старшин.
Гладышев поздравил Абдулхаира с избранием на ханство. На это поздравление хан ответил: «Я благодарю Аллаха за то, что Хива отныне находится в подданстве русской императрицы».
Окружавшие хана хивинцы хмуро молчали, явно не разделяя его оптимизма по этому поводу. Покончив с формальными приветствиями, хан перешел к делу. Ему нужны были люди из отряда Гладышева, чтобы послать их к шаху Надиру с письмом, в котором объявлено было бы, что хан Абдулхаир, подданный русской императрицы, принял под свое начало город Хиву, дабы подчинить его русской государыне. Атак как шах является союзником русской короны, то «разорения ради того города ходить бы не изволил».
