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