6-го августа Кирилов достиг р. Яика при устье р Орь. Здесь к нему явились представители казакского народа, при помощи которых ему удалось заготовить запасы продовольственного скота для Экспедиции и таким образом предотвратить голод в отряде до прибытия транспорта из Сибири, навстречу которому он выслал особый отряд.
15-го августа Кирилов заложил гор. Оренбург, который должен был стать оплотом русского господства во вновь присоединенной окраине.
Вначале гор. Оренбург представлял собою небольшую крепостцу о четырех бастионах, с малой цитаделью, которая была расположена на горе Преображенской, названной так в память прибытия Экспедиции в день Преображения 6-го августа.
Между тем восстание в Башкирии разгоралось. До Кирилова доходили сведения, что восставшие поднимают весь народ. При таком положении оставаться в г. Оренбурге, отрезанном от внешнего мира, было опасно. Кирилов командировал в Верхне-Яицкую пристань отряд под командой полковника Тевкелева, поручив ему снабдить город Оренбург продовольствием из Сибири.
Оставив в г. Оренбурге гарнизон из 10 рот под командой полковника Чемадурова, Кирилов с остальным отрядом выступил по направлению в Сакмарский городок, имея целью идти к городу Мензелинску, куда спешил к нему на помощь из Казани с отрядом войск генерал Румянцев.
Сакмарский городок уже существовал в это время. Он был построен яицкими казаками в 1725 г. и представлял собой маленькое укрепление, с земляным валом и рвом и одной деревянной башней. Местоположение городка было выбрано весьма удачно: он был прекрасно защищен окружающими его горами. В городке жило до 200 яицких казаков и 50 инородцев, которые занимались земледелием. Городок неоднократно подвергался нападениям со стороны казаков и башкир, но всякий раз мужественно отбивал эти нападения.
Кирилов прибыл благополучно в Сакмарский городок, где к нему были доставлены видные вожди башкирского восстания Асунагул Кильмакаев и несколько его товарищей, которые были казнены.
Из Сакмарского городка Кирилов выступил по направлению к Уфе. Не доходя до г. Уфы, он встретил до 600 восставших башкир под предводительством старшины Атай Кусюмова и разбил их. Продолжая свой движения вперед, Кирилов приказал сжигать на пути все башкирские деревни, забирая и уничтожая продовольствие и скот, чтобы обречь восставших на голодную смерть.
Между тем полковник Тевкелев со своим отрядом прибыл в Верхне-Яицкую крепость, из которой направился к Теченской слободе и далее в Сибирь для заготовки продовольствия для Оренбурга. На р. Ае, впадавшей в Уфу, Тевкелев был атакован восставшими башкирами, но отбил их и начал неслыханно-суровую и беспощадную расправу с восставшими. Он уничтожил до 50 башкирских сел, поголовно истребляя жителей: башкир загоняли в пустые амбары и сжигали живьем. Расправа Тевкелева вызвала всеобщее восстание народа.
Правительство, опасаясь за участь Оренбургской Экспедиции, приняло энергичные меры для подавления нового башкирского восстания. В Оренбургский край были двинуты значительные военные силы с Дона, с Волги и с Яика, до 6 т. казаков и калмыков, которые и вторгнулись с разных сторон в Башкирию.
Командующим войсками, действующими против башкир, был назначен генерал майор Румянцев: 19 сентября он прибыл в г. Мензелинск, где к нему присоединился с своим отрядом статский советник Кирилов.
Между тем правительство в наказание башкирам за их мятежнические выступления приняло ряд мер, направленных к ограничению их земельных прав и привилегий, дарованных царем Иваном IV.
Первой мерой правительства явился указ 11 февраля 1736 г., разрешивший покупать и арендовать у башкир земли. Указ широко открыл двери колонизационному потоку русских переселенцев в Башкирию. Помещики, государственные крестьяне, промышленники и купцы двинулись в Башкирию и начали покупать и кортомить (т. е. брать в долгосрочную аренду) башкирские земли под пашни и заводы. При покупке земли границы ее определялись урочищами, без обозначения количества десятин. При отводе земель под заводы и русским поселенцам, случалось, отходили бортовые деревья, сенокосные угодья и пашни башкир.
С приливом новой волны русской колонизации башкиры почувствовали еще более «несносное притеснение» и стали приходить по их словам в «убожество» и бедное состояние.
Во-вторых, все башкирские тарханы были лишены своих прежних привилегий и обращены в «ясашных», т. е. были обязаны платить ясак наравне со всеми другими башкирами. Весь пришлый элемент края — мещеряки, тептяри и другие инородцы, оставшиеся верные правительству, не только были освобождены от уплаты башкирам денег за аренду у них земли, но и наделены землею башкир, принимавших участие в восстании, и сравнены во всех правах с коренным населением Башкирии. Затем правительство приняло ряд мер чисто охранного характера. Башкирам было запрещено собираться на сходки и съезды, вступать в родство с татарами, строить мечети и открывать при них школы. За каждую свадьбу башкиры были обязаны платить налог лошадьми; в башкирских селах были закрыты все кузницы, во избежение того, что башкиры могут в них приготовлять себе холодное оружие и т. д.
Кирилов не довольствовался этими мерами охранного порядка и настаивал на том, «чтобы воров башкирцев утеснять, разоряя сплошь», тогда как генерал Румянцев был склонен действовать против башкир более гуманными мерами.
Мнение Кирилова получило перевес и было утверждено правительством, которое предписало генералу Румянцеву принять самые решительные меры для подавления восстания.
С наступлением весны 1736 г. Румянцев получил в свое распоряжение несколько полков о Царицынской линии и начал наступление на Башкирию, предавая огню и мечу все башкирские села по Сибирской и Осинской дорогам.
На Ногайской дороге свирепствовал Кирилов, истребивший до 200 башкирских сел. Охваченные паникой башкиры бежали в горы.
Главный вождь башкир — старшина Кильмяк Абыз собрал около себя до 8000 башкир и 29 июня окружил лагерь генерала Румянцева на р. Белой, но был отбит.
Яицкие казаки встретились с башкирами на реке Казе. Между ними произошло жестокое сражение, в котором башкиры были разбиты. Казаки выжгли до 200 деревень по реке Ику. На реке Неке казаки и башкиры встретились вновь. Бой продолжался с утра до вечера и кончился снова победой казаков. Под Табынском казаки разбили башкир в третий раз.
К концу 1736 г. восстание башкир на Ногайской и Сибирской дорогах было подавлено. Главные вожди восстания Кильмяк Абыз и Акай Кусюмов были схвачены и казнены. Села восставших выжжены, и несчастный народ погибал от холода и голода. В Мензелинске, Сакмарске, Уфе и других городах происходили массовые казни участников восстания, которые должны были терроризовать население.
Покончив с восстанием, Кирилов назначил в Башкирии старшин, сотских и десятских из приверженцев России и обложил население тяжелой данью, обязав поставлять бесплатно продовольствие и фураж для войск.
Однако, несмотря на видимое успокоение края, Кирилов не решился вернуться в г. Оренбург, а выбрал для своего пребывания гор. Самару.
Между тем гарнизон города Оренбурга, отрезанный восставшими башкирами от Уфы и Сибири, голодал.
Верхне-Яицкая пристань была взята башкирами и срыта до основания. Подвоза продовольствия из Сибири не было.
На помощь Оренбургскому гарнизону из Сакмарского городка был командирован с продовольствием отряд премьер-майора Останкова, который, двигаясь к Оренбургу, заложил вторую по реке Яику крепость после Оренбурга — Верхне-Озерную и оставил в ней гарнизон из одной роты драгун, полуроты пехоты и 50 жалованных казаков из русских и татар и добровольцев яицких казаков.
Доставив в г. Оренбург продовольствие, Останков был назначен комендантом этого города.
Воспользовавшись затишьем восстания, Кирилов энергично приступил к постройке ряда новых крепостей по р.р. Сакмаре, Самаре, Яику и Миясу. К 27 октября 1736 г. в Оренбургском крае уже было заложено 21 укрепление. Наиболее известные из них: Оренбург (ныне г. Орск). Губерлинское, Озерное и форпосты: Бердский, Сорочий и Тоцкий. Кроме того в крае были построены укрепления: Бузулукское, Табынское, Красно-Уфимское, Ельдяцкое, Миясское и Чебаркульское.
Крепости обычно обносились земляным валом со рвом и башнями или огораживались рогатками и частоколом; на валу ставились чугунные и медные пушки.
Первое население вновь возведенных крепостей было крайне разнообразно. Здесь были уфимские, яицкие, самарские казаки, крещеные и некрещеные ногайцы, татары и другие инородцы, ссыльные и беглые крестьяне из разных мест.
За своей смертью Кирилов не успел выполнить свои планы по военному устройству Оренбургского края.