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