Из дворян и иноземцев Кирилов формирует несколько рот Оренбургского драгунского полка. В Уфе и Сибири заготавливается провиант и другие припасы для экспедиции. С целью облегчения подвоза оных товаров из Сибири в срочном порядке в верховьях Яика закладывается Верхнеяицкая пристань (будущий город Верхнеуральск). Две роты солдат Уфимского полка во главе с подполковником Арсеньевым и небольшое количество казаков составляют ее гарнизон.

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

11 апреля 1735 года его отряд из 15 регулярных рот, 350 казаков, 600 мещеряков и сотни башкир при 26 орудиях и 32 мортирах выступает из Уфы и, перейдя реку Белую, становится лагерем на реке Чесноковке. Сюда должен подойти еще Вологодский драгунский полк под командованием подполковника Чирикова с Камской линии. По непонятным причинам, скорей всего из-за разбросанности полка между Ставрополем, Елабугой, Бирском и Мензелинском, подход драгун задерживается.

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

Кирилов принимает срочные меры, стараясь обезопасить, прежде всего, фланги. Со стороны Сибирского тракта он приказывает срочно заложить два форпоста — крепостцы Елдецкую и Красноуфимскую, по Ногайскому тракту укрепляется город Табынск, в 85 верстах от Уфы. Атаману Черному в Самару предписывается усилить казачьи разъезды вдоль реки Самары, дабы следить за действиями башкир на Ногайском тракте с тылу.

Простояв почти два месяца на месте, так и не дождавшись вологодских драгун, Кирилов принимает решение выступать без них. Подполковник Чириков подходит к оставленному лагерю лишь четыре дня спустя. Простояв еще около девяти дней, драгуны Чирикова начинают двигаться по следам экспедиции. Неделю они шли без приключений, но в 160 верстах от Уфы полк был внезапно атакован башкирами. Погиб сам командир подполковник Чириков, полковой священник и 18 драгун (по другим данным — 60). Часть обоза была разграблена (46 повозок).

Вместе с известием о поражении Вологодского полка Кирилов узнает, что подвергся нападению и обоз с провиантом, шедший из сибирских городков к Верхнеяицкой пристани. 40 возов было разграблено и отбито, остальные загородились и выдержали осаду. На помощь к ним пришли две роты Уфимского полка подполковника Арсеньева.

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

6-го августа экспедиция прибыла к устью реки Орь. Уже ощущался недостаток в продовольствии. Пришлось забить часть лошадей и пустить их на прокорм. 15-го августа была заложена крепость, 30-го введен гарнизон, 31-го после молебна и трехкратного орудийного салюта было положено основание городу Оренбургу «о девяти бастионах».

Уже через неделю Кирилов отправляется назад в Уфу, оставив в Оренбурге подполковника Чемодурова с десятью ротами пехоты и 150 казаками. Еще один отряд он отправляет в сибирские городки для заготовки провианта и доставки его к Верхнеяицкой пристани. Зима в этом году была ранняя и очень суровая. Очередной обоз, шедший в Оренбург, был вновь разграблен башкирами. Угроза голодной смерти для гарнизона была уже очевидной. Подполковник Чемоданов отправляет 800 человек к Верхнеяицкой пристани, где имелся значительный запас хлеба. Но из-за сильных морозов и пурги, пройдя за три дня всего тридцать верст, отряд вернулся, потеряв пять человек замерзшими насмерть и 150 обмороженными. Тогда Чемодуров пытается достичь Сакмарского городка, располагавшегося в 265 верстах вниз по течению Яика, и отправляет туда 773 человека. Этот отряд ждала еще худшая участь. Более пятисот погибло в пути от голода и морозов, а из двухсот дошедших более восьмидесяти были с отмороженными конечностями.

Вместе с этим, башкирский бунт не прекращался. Правительство направляет на его усмирение генерала Александра Румянцева и выделяет дополнительные силы в виде 3000 калмыков, 1000 донских и 2000 яицких казаков. Кирилов получает указ во всем повиноваться генералу Румянцеву. В декабре они встречаются и совместно разрабатывают план по усмирению края.

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

Прибыв в Петербург в начале 1736 года, Кирилов представил Императрице свое особое предложение об устройстве края. Суть его сводилась к необходимости охватить все окраины, населенные башкирами, непрерывной цепью крепостей на юге, востоке и севере. Тем самым прекратить всякое общение их со всеми остальными кочевниками. Помимо этого, следовало завести собственные войска по примеру южных рубежей отечества, где находились слободские и ландмилицейские полки. Такие полномочия Кирилову были даны. Разрешалось брать на службу даже беглых, живущих среди яицких казаков, расселять их по новым крепостям. Правда, это разрешение просуществовало недолго, до 20 августа 1739 года, когда вновь Высочайшим Указом было определено, что поселенных беглых возвращать их помещикам.

1736 год прошел в непрерывных боях с мятежными башкирами. 24 марта Кирилов разбил их между реками Белой, Уршаку, Кегушу и Тору. Уничтожено было до 700 человек, 158 казнено, 160 взято в плен. Сожжено 200 деревень в 4000 дворов.

Действуя самостоятельно, Румянцев на Сибирской и Осинской дорогах разорил несколько десятков деревень и уничтожил около 2000 башкир. В апреле Румянцев пошел далее, по реке Деме, выжег еще сотню деревень, около тысячи побил, в плен взял двести человек. К генералу явились с повинной башкирские старшины Акай Кусюмов и Султан-Мурад со 120 своими людьми. Однако Румянцев их арестовал и пошел дальше. Позднее он отпустил обоих с обещанием уговорить хана Ногайской Орды — Кильмяк-Абыза, одного из самых одиозных вожаков башкир, сложить оружие. Но обещание выполнено не было, и башкиры, соединившись, попытались снова атаковать Румянцева. В результате русские отбили башкир и отбросили в степи.

В этом же году Кирилов закладывает еще несколько крепостей вдоль реки Самары, по старому казацкому шляху, получившему потом название Новомосковский тракт. Это крепости Чернореченская, Камыш-Самарская, Переволоцкая пристань, Сорочинская, Тоцкая, Бузулукская и Бердская (будущий Оренбург, а саму Бердскую перенесут на реку Сакмару, и станет она в свое время столицей Пугачевской).

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

В самый разгар боев с башкирами последовал указ Миниха об отправке из его армии двух драгунских полков — Вятского и Ростовского — в распоряжение Румянцева. С ними шли тогда Алеша Веселовский да знакомый его старый, полковник Данила Павлов, командир ростовцев. Но, как мы помним, волнения утихли, полки были остановлены на зимние квартиры под Ельцом. Тогда-то и вступил в командование Вятским полком Иван Семенович Тютчев, тогда-то и произошло их знакомство. А теперь Алеша ехал со своей женой, дочкой Тютчева, в те же самые места, куда не дошел их полк три года назад.