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