В 1733 году Тевкелев побратался с Абдулхаиром, став его «тамыром» – названым братом, – и привез с собою в Уфу его сына Эрали-султана, старшин Средней и Большой Орд, а также представителей каракалпаков. Эту делегацию отвезли в Петербург, где идея построения города на реке Ори была поддержана обер-секретарем и тайным советником Иваном Кирилловичем Кирилловым, подавшим в Сенат проект, который был одобрен и по которому 1 мая 1734 года последовало распоряжение императрицы Анны Иоанновны, поручившей строительство Кириллову.
15 июня Тевкелев и Кириллов выехали из столицы во главе целой экспедиции назначенных к новому месту службы чиновников и военных, морских офицеров – для устроения будущего порта на Аральском море и геодезистов – для планировки города. В Москве прихватили священника, нескольких студентов Славяно-греко-латинской академии, лекаря, натуралиста, горного инженера. К месту строительства нагнали людей, войска, и вскоре город, названный Орском, стал расти буквально на пустом месте. Оттуда формально управлялись земли степных владык, составлявшие значительную часть современного Казахстана – до Аральского моря включительно. Фактически эти земли никому не подчинялись, это была все та же степь, жившая все по тем же законам грабежа и насилия. Но именно к ней и были обращены помыслы тех, кто желал укрепить русское владычество над караванными путями. Еще в год основания Орска от того места, где более тысячи рабочих строили крепость и новый город, в степь отправилась команда топографов под командой геодезиста Муравина; они имели все то же задание: отыскать надежный путь к Хиве. Эта экспедиция приготовила разборные суда на Яике, чтобы перенести их на Арал и исследовать берега этого моря. Но планам этим не дано было осуществиться, хотя несколькими годами позже Муравин дошел-таки до Хивы, где он и его товарищи оказались в самом центре интриг «восточной политики». Эти похождения русских в Хиве требуют отдельного рассказа.
В 1739 году Абдулхаир, кочевавший в степях между Оренбургом и Аральским морем, известил русское правительство, в подданстве которого состоял с 1731 года, о желании построить новый город с крепостью возле реки Сыр и просил прислать туда постоянный гарнизон. Этому обращению Абдулхаира к русской императрице предшествовала череда событий, совершенно запутавших политическую ситуацию вокруг Хивы.
Хивинский хан Ильбарс Третий, в 1728 году наследовавший ханство после смерти коварного Ширгози, в финале своего правления подвергся атаке с двух сторон. Почти одновременно к нему прибыли два посольства: от хана бухарского Абул-Феиза и персидского шаха Надира. Оба посольства требовали выражения покорности. Ильбарс же, будучи настоящим хивинским ханом, поступил так, как и принято было в этом ханстве: он решил не покоряться ни тому и ни другому, а оба посольства распорядился умертвить самым коварным образом.
Узнав о том, что его посольство вырезали, Надир-шах, стоявший с войсками под Чарджоу, пошел в поход на Хиву, а ему навстречу выступил с войском Ильбарс. Шах запер хивинского хана в крепости Ханки, находившейся в тридцати пяти верстах от Хивы, и в конце концов взял крепость. По приказу Надир-шаха Ильбарса и тридцать его приближенных, в отместку за уничтожение послов, живыми закопали в землю.
Перепуганные суровостью шаха, хивинцы отправили послов к Абдулхаиру с просьбой стать ханом. Они надеялись, что Надир-шах не посмеет напасть на подданного русской короны. Однако Абдулхаир, опасаясь, что хивинцы замыслили очередное коварство и выдадут его Надир-шаху, отказался покинуть родные стойбища и со всей возможной энергией принялся обозначать свою лояльность русским.
Обрадованная столь похвальными устремлениями, императрица 20 августа 1739 года подписала указ о немедленной посылке к хану людей для выбора места построения крепости. Исполнение этого поручения было возложено на поручика Оренбургского драгунского полка Дмитрия Гладышева, знавшего татарский язык; ему были вручены грамота от императрицы и письмо от князя Урусова, которые он должен был вручить хану. Для съемок местности с ним ехали геодезист Муравин, инженерный надзиратель Назимов и переводчик Усман Арасланов. Для конвоя им дан был небольшой отряд казаков.
