Оставшиеся в Джунгарии после ухода калмыков племена, входившие в Ойратский Союз, составили сильное Джунгарское ханство, которое, расширяя свои владения, вступило в борьбу со своими соседями — казак-киргизами.
В начале XVIII в. Джунгарское ханство настолько усилилось, что его границы простирались от Алтая до Аральского моря, занимая южную часть Семипалатинской и Акмолинской губ.
Зимою в 1723 г. джунгары под предводительством своего хана Галдан Цирена напали на кочевья казак-киргизов, отвоевали у них города Ташкент, Туркестан и Сайрам. Казаки были отброшены ими в голодные степи Туркестана, к пределам Хивы и Бухары.
Страдая от недостатка кормов и зимней непогоды, теряя массу людей и скота, казаки объединились под властью султана Абулхаира, впоследствие ставшего ханом Малой Орды. Общими усилиями они отбросили джунгар из части прежних своих кочевий, но удержаться в них не могли. Возникшие родовые распри ослабили военную силу казаков. Не будучи в состоянии одолеть джунгар, казаки Средней и Малой орды двинулись на запад и северо-запад и достигли берегов р. Урала, оттеснив из зауральных степей башкир и калмыков.
Захватив степи по правому берегу р. Урала, казаки были вынуждены вступить за обладание ими в упорную борьбу с калмыками и башкирами, отбивая в то же время на востоке теснивших их джунгар.
Изнемогая в борьбе с врагами, которые стиснули их со всех сторон, казаки Малой орды во главе с Абулхаир-ханом решили искать подданства и защиты у русского царя.
В 1730 г. Абулхаир-хан отправил свое посольство из казакских старшин в г. Уфу, к воеводе Бутурлину, и просил его довести просьбу о подданстве казакского народа до царицы.
Из Уфы послы казакского хана были отправлены в Петербург и приняты при дворе царицы Анны Ивановны.
Добровольное принятие русского подданства Абулхаир-ханом как нельзя кстати отвечало видам русского торгового капитала, который, как мы видели, стремился завладеть казак-киргизскими степями еще со времени Петра I.
Изъявив согласие на прием Абулхаир-хана в свое подданство русское правительство снарядило к нему особое посольство, во главе которого был поставлен Мурза Тевкелев, переводчик Коллегии иностранных дел.
Тевкелев с посольством прибыл в орду, но, сверхожидания, был встречен весьма враждебно народом, который, как оказалось, не желал принимать русское подданство. Царское посольство было задержано в орде в качестве заложников.
Около 2-х лет Тевкелев пробыл в кочевьях Малой орды, в качестве невольного гостя, «испытывая смертельную опасность и голодание», пока ему не удалось путем подкупа и силой убеждения своего редкого красноречия склонить казакских старшин принять русское подданство.
В 1733 г. на одном из народных казакских съездов вопрос о принятии русского подданства был решен в положительном смысле и ханы — Малой орды Абулхаир, Средней орды — Семеке, а также Каракалпакский хан — присягнули на верность России
В начале 1734 г. Тевкелев вернулся в Петербург в сопровождении нового казакского посольства, во главе которого на этот раз стоял старший сын Абулхаир-хана султан Эрали.
Казакские орды были приняты в русское подданство. Для управления вновь присоединенным краем правительство, по просьбе Абулхаир-хана, решило построить новый город на р. Урале (Яике), в устье р. Орь.
Статский советник Кирилов, по поручению правительства, разработал положение об управлении Оренбургским краем, о постройке пограничных крепостей, об основании порта на Аральском море, с устройством на нем судоходства для торговых сношений с среднеазиатскими странами.
7-го июня 1734 года проект Кирилова был утвержден, а он сам назначен командиром Оренбургской Экспедиции, на которую было возложено осуществление этого проекта.