По Рычкову, задолго до того, как Иван Грозный принял башкир под свою высокую руку и выдал им грамоту на владение всею их землею на вечные времена, они терпели притеснения и обиды от казанских татар, сибирских ханов и казахских феодалов. Башкиры особо ценили свободу и независимость, жили как вольные кочевники в юртах, разводили лошадей, крупный рогатый скот, пчел, ясак платили звериными шкурами, медом и деньгами (по 25 копеек в год с каждой юрты). А те башкиры, что несли воинскую службу, от налога освобождались. Во главе родовых общин стояли старшины-феодалы, но с ограниченной властью: важные дела обсуждались в народном собрании (джине), где каждый башкир имел право голоса.

Спасаясь от разорительных набегов соседних племен, башкиры попросили у русского царя построить на их земле город. В 1586 году воевода Иван Нагой приступил к основанию города Уфы, который был первым русским поселением в Башкирии. В том же году на волжском берегу русские заложили Самару, вопреки воле ногайского князя Уруса. Еще раньше на восточных оконечностях башкирской территории, на стыке ее с русскими землями, были поставлены крепости Мензелинск и Челябинск. Кроме них, по берегам Урала, Волги, Камы сооружались укрепления, остроги, зимовья. Они заполнялись войсками и русскими поселенцами, которым выдавались земельные участки.

Но жалованная грамота Ивана Грозного, а позже и Соборное Уложение 1649 года запрещали русским не только приобретать башкирские земли, но даже и арендовать их. Однако на местах все обстояло иначе. Башкиры гневались, обвиняли русское правительство в нарушении своих же указов, слали в Москву депутации с жалобами на «налоги и обиды». Не нравились им и распоряжения русского царя регулярно поставлять для армии и охраны границ лошадей и конных воинов. Башкирские феодалы привыкли считать себя вольными слугами, их возмущали какие-либо меры принуждения. Признавая силу русского государства и желая при случае опереться на нее, они все же тяготились централизованной властью.

С неприязнью и страхом смотрели они на то, как окружают и расчленяют их землю опорными пунктами крепостей и форпостов, сетью рудников и заводов.

Вот почему, узнав о намерении Кирилова строить в их владениях еще один большой город, они возмутились и решили сопротивляться.

Кирилов всю зиму 1735 года энергично готовился к закладке города, запасался строительными материалами, набирал каменщиков, плотников, архитекторов. 11 апреля во главе отряда он выступил в поход на реку Орь — приток Яика, где намечалось строительство. Пятисотверстный путь отряда пролегал с севера на юг через самую заселенную часть Башкирии, и едва он отошел на десяток верст от Уфы, как всюду зловеще замаячили разъезды вооруженных конников-башкир. Имея при себе пятнадцать рот солдат, 350 казаков, обоз с провиантом и артиллерией, Кирилов решил подождать подхода драгунского полка.

Меж тем отовсюду поступали тревожные вести о готовящемся восстании башкир. Кирилов не верил слухам. Так и не дождавшись вологодского войска, он отдал команду полковнику Тевкелеву, своему помощнику в военных делах, поднимать отряд и двигаться дальше. Как потом выяснилось, на драгун напал крупный отряд башкир, в итоге подполковник Чириков и с ним 60 человек были убиты, 46 обозных повозок захвачены и разграблены.

К Кирилову приехали башкирские послы и опять предложили отказаться от похода. Кирилов был непреклонен, отряд русских медленно, но упорно шел к намеченной цели. По ночам, однако, стали бесследно исчезать часовые, фураж, продукты, лошади…

К трудностям и внешним неприятелям экспедиционного отряда в пути прибавился еще и «внутренний неприятель» — голод. Взятый в Уфе провиант кончился еще до прибытия на реку Орь.

Измученный отряд терпел многие лишения еще и оттого, что продвигался по незнакомой местности. Надо было обойти Губерлинские горы, лежащие в пятидесяти верстах от устья Ори. Команда же Кирилова двинулась напрямую и, по словам Рычкова, будучи в этих горах, «от крутостей и ущельев оных в переходе через них имела такое великое затруднение, что большая часть артиллерии и тяжелого багажа, переломавши колеса и несмотря на большую тогда от башкирцев опасность, принуждена была в разных ущелинах ночевать, и уж на другой день с превеликим трудом на степь выправилась».

Башкирские проводники, которых нанял Кирилов за большое вознаграждение, умышленно утаили известный им удобный путь проезда к Ори, на каждом шагу чиня отряду всяческие помехи.

Опасаясь, что «башкирское возмущение» может помешать делу экспедиции, Кирилов обратился в Кабинет министров за помощью.

«Если никакие резоны не годятся, — писал он, — то напрасно я в таком великом деле азарт на себя взял, ибо тремя батальонами, со мною на первый случай посланными, обнять и в вечном владении утвердить две провинции нельзя».

Прося военной помощи, Кирилов, однако, старался убедить колеблющееся правительство в том, что налет башкир на Вологодский драгунский полк — всего лишь «малое воровское нападение», из-за чего нет нужды останавливать «к великой славе зачатое дело».

В начале августа отряд Кирилова все же достиг устья Ори, места впадения реки в Яик (Урал), и приступил к сооружению крепостных стен. 31 августа после богослужения и артиллерийского салюта — трех залпов пушечных батарей — был заложен и сам Оренбург. Город-крепость с девятью бастионами.

Оставив в нем небольшой гарнизон и ограниченный запас продовольствия, Кирилов 7 сентября двинулся в обратный путь. На отряд полуголодных солдат и казаков все чаще наскакивали шайки лихих наездников. Они внезапно появлялись из засады и, осыпав отряд стрелами, исчезали. В 130 верстах от Уфы русскую экспедицию атаковали орды башкирской конницы Акая Кусумова. Это открытое вооруженное столкновение, десятки убитых и раненых заставили Кирилова серьезно озаботиться и принять контрмеры. Прибыв в Уфу, он направил в Сенат доношение о начале башкирского восстания. На помощь Кирилову спешно было послано войско под командованием генерал-лейтенанта Алексея Ивановича Румянцева с наказом действовать уговорами и только в крайних случаях — оружием.

По прибытии в Уфу Румянцев разослал башкирам манифесты, призывая их прекратить бунт и явиться с повинною. Мятежники продолжали нападать на армейские гарнизоны и поселения русских, портили строения, сжигали мосты и крепостные ограждения, грабили обозы русских купцов. Особенно свирепствовал отряд Кильмяка Нурушева. Чтобы избежать многие кровопролития, Румянцев отпустил пленного старшину Салтана Мурата, послав его уговорить Кильмяка повиниться. Но Мурат присоединился к восставшим, и вскоре восьмитысячный отряд башкир внезапно напал на лагерь Румянцева, убив 180 солдат и 160 ранив.

В ноябре 1735 года повстанцы перекрыли дорогу в Оренбург большому продовольственному обозу, в итоге несколько сот солдат, не дождавшись провианта, умерли в крепости от голода.

И тогда Кирилов двинул против восставших карательные отряды. При ожесточенных схватках с регулярными войсками башкирские конники почти всегда несли поражения, десятками попадали в плен. Злостных бунтовщиков вешали, сажали на колья, до смерти засекали розгами, ссылали на каторгу. А тех, кто приходил с повинной, отпускали домой, но с условием, чтобы каждый принял присягу в верности и уплатил одну лошадь в качестве штрафа. Румянцев требовал запретить во всех селениях башкирам «носить ружья и по домам иметь; в уездах кузниц и кузнецов не иметь, магазины наполнить провиантом».

К зиме восстание поутихло. Но русское правительство держало ухо востро. Оно понимало, что в Башкирии нужны не только войска. Важно было привлечь на новые земли купечество, ремесленных людей, хлебопашцев. С этой целью Сенат указом от 11 февраля 1736 года определил весомые льготы всем переселенцам. Кроме ранее объявленных «Привилегий городу Оренбургу», дававших право селиться в нем людям всяких вер и званий, вышеназванный указ разрешил новоселам приобретать и «крепить за собой» земельные угодья на всей башкирской территории. Планировалось поселить при Оренбурге и других городах более тысячи яицких казаков, построить Табынскую, Сорочинскую, Бузулукскую, Борскую, Сакмарскую крепости, десятки форпостов и укреплений, три медеплавильных завода и множество других военно-хозяйственных объектов.