В 1730 году при правлении государыни императрицы Анны Иоанновны прислал в Уфу посольство к воеводе Бурлину, прося принять его в русское подданство, теснимый соседними племенами хан Малой Киргизской Орды Абдулхаир. Весной 1731 года к нему для переговоров был направлен «старший переводчик по секретным делам» мурза Алексей Тевкелев, сделавший карьеру «по части секретной дипломатии» еще во времена Петра Великого. Он сумел убедить киргизов в пользе русского покровительства и тех выгодах, которые сулит заложение в степи города; из него, дескать, легко будет торговать с киргизами и прийти им на помощь, если нападут враги.

В 1733 году Тевкелев побратался с Абдулхаиром, став его «тамыром» — названым братом, — и привез с собою в Уфу его сына Эрали-султана, старшин Средней и Большой Орд, а также представителей каракалпаков. Эту делегацию отвезли в Петербург, где идея построения города на реке Ори была поддержана обер-секретарем и тайным советником Иваном Кирилловичем Кирилловым, подавшим в Сенат проект, который был одобрен и по которому 1 мая 1734 года последовало распоряжение императрицы Анны Иоанновны, поручившей строительство Кириллову.

15 июня Тевкелев и Кириллов выехали из столицы во главе целой экспедиции назначенных к новому месту службы чиновников и военных, морских офицеров — для устроения будущего порта на Аральском море и геодезистов — для планировки города. В Москве прихватили священника, нескольких студентов Славяно-греко-латинской академии, лекаря, натуралиста, горного инженера. К месту строительства нагнали людей, войска, и вскоре город, названный Орском, стал расти буквально на пустом месте. Оттуда формально управлялись земли степных владык, составлявшие значительную часть современного Казахстана — до Аральского моря включительно. Фактически эти земли никому не подчинялись, это была все та же степь, жившая все по тем же законам грабежа и насилия. Но именно к ней и были обращены помыслы тех, кто желал укрепить русское владычество над караванными путями. Еще в год основания Орска от того места, где более тысячи рабочих строили крепость и новый город, в степь отправилась команда топографов под командой геодезиста Муравина; они имели все то же задание: отыскать надежный путь к Хиве. Эта экспедиция приготовила разборные суда на Яике, чтобы перенести их на Арал и исследовать берега этого моря. Но планам этим не дано было осуществиться, хотя несколькими годами позже Муравин дошел-таки до Хивы, где он и его товарищи оказались в самом центре интриг «восточной политики». Эти похождения русских в Хиве требуют отдельного рассказа.

В 1739 году Абдулхаир, кочевавший в степях между Оренбургом и Аральским морем, известил русское правительство, в подданстве которого состоял с 1731 года, о желании построить новый город с крепостью возле реки Сыр и просил прислать туда постоянный гарнизон. Этому обращению Абдулхаира к русской императрице предшествовала череда событий, совершенно запутавших политическую ситуацию вокруг Хивы.

Хивинский хан Ильбарс Третий, в 1728 году наследовавший ханство после смерти коварного Ширгози, в финале своего правления подвергся атаке с двух сторон. Почти одновременно к нему прибыли два посольства: от хана бухарского Абул-Феиза и персидского шаха Надира. Оба посольства требовали выражения покорности. Ильбарс же, будучи настоящим хивинским ханом, поступил так, как и принято было в этом ханстве: он решил не покоряться ни тому и ни другому, а оба посольства распорядился умертвить самым коварным образом.

Узнав о том, что его посольство вырезали, Надир-шах, стоявший с войсками под Чарджоу, пошел в поход на Хиву, а ему навстречу выступил с войском Ильбарс. Шах запер хивинского хана в крепости Ханки, находившейся в тридцати пяти верстах от Хивы, и в конце концов взял крепость. По приказу Надир-шаха Ильбарса и тридцать его приближенных, в отместку за уничтожение послов, живыми закопали в землю.

Перепуганные суровостью шаха, хивинцы отправили послов к Абдулхаиру с просьбой стать ханом. Они надеялись, что Надир-шах не посмеет напасть на подданного русской короны. Однако Абдулхаир, опасаясь, что хивинцы замыслили очередное коварство и выдадут его Надир-шаху, отказался покинуть родные стойбища и со всей возможной энергией принялся обозначать свою лояльность русским.

Обрадованная столь похвальными устремлениями, императрица 20 августа 1739 года подписала указ о немедленной посылке к хану людей для выбора места построения крепости. Исполнение этого поручения было возложено на поручика Оренбургского драгунского полка Дмитрия Гладышева, знавшего татарский язык; ему были вручены грамота от императрицы и письмо от князя Урусова, которые он должен был вручить хану. Для съемок местности с ним ехали геодезист Муравин, инженерный надзиратель Назимов и переводчик Усман Арасланов. Для конвоя им дан был небольшой отряд казаков.

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

Прибыв в ханское кочевье, Гладышев и его люди самого Абдулхаира не застали, а потому передали подарки, присланные для хана от казны, его жене ханше Пупайе и старшему сыну Нурали-султану, который специально ждал русских, чтобы сопроводить их к отцу, предусмотрительно державшемуся подальше от кочевья. С Нурали были его дядя Нияз, который прежде ездил с Тевкелевым в Петербург, и шестеро телохранителей хана.

Отдохнув четыре дня в гостях у ханши, отряд Гладышева с Нурали-султаном и Ниязом отправился в степную ставку хана. «Здесь известно, — сказал ему Абдулхаир, — что персидский шах Надир идет на Хиву. Мне же хочется, чтобы город этот был под властью ее императорского величества. Сего ради намерен я ехать в Хиву, и чтобы ты был при мне. Оттуда отправишься навстречу шаху и покажешь ему присланную мне ее величеством грамоту с тем, чтобы шах со мною не ссорился». Гладышев отвечал на это, что коли прислан к нему, то и должен поступать по его ханскому приказу.

Переночевав в ханской ставке, наутро Гладышев и его люди присоединились к ханскому конвою, состоявшему из 3 тысяч нукеров, набранных из киргизов, каракалпаков и аральцев. Снявшись со стоянки, хан выступил на Хиву, добравшись к вечеру до перевоза на реке Улударье, имевшей в этом месте ширину более 150 метров. На берегу были заготовлены двадцать больших лодок для переправы. Возле них и заночевали. Утром начали переправляться, ставя по три-четыре лошади в лодку, а иных пуская вплавь; закончили переправу 4 ноября. К тому времени на хивинский берег прибыла делегация из двух десятков хивинских вельмож во главе со знатным узбеком Авест-Мираном. Хивинские чины слезно просили хана как можно скорее прибыть в город, поскольку им достоверно известно, что шах собирается идти на Хиву. Абдулхаир внял их просьбам и выступил столь поспешно, что русские отстали в степи и долго плутали по ней, прежде чем вышли к городу. Там они узнали, что Абдулхаир уже принял ханство.