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