Закончив приготовления Экспедиция Кирилова 11 апреля 1735 года выступила из г. Уфы. Отряд Кирилова состоял из 15 рот пехоты, 350 самарских и уфимских казаков, 600 мещеряков, 100 башкир, нескольких новокрещенных татар и калмыков, при 23 медных пушках и 32 мортирах. Отряд двигался двумя колоннами. Впереди шла первая колонна под командой самого Кирилова, а сзади него на некотором расстоянии двигался Вологодский пехотный полк, под командой полковника Чирикова.
Проникнув в намерение русских построить новый город на южной границе Башкирии, башкиры решили не допустить Экспедицию Кирилова к месту назначения. На одном из переходов к Кирилову явились два башкирских старшины и потребовали, чтобы Экспедиция вернулась обратно, так как они не допустят построить город на их земле.
Кирилов приказал схватить представителей народа и предать их жестокой пытке. Во время пыток один из башкир умер. Экспедиция продолжала свое движение вперед. В 160 в. от г. Уфы, башкиры Юрмантынской волости Ногайской дороги, под предводительством старшины Кильмяка Абыза, напали на отряд Чирикова и отбили у него часть обоза. В происшедшей стычке сам полковник Чириков, несколько драгун и служащих были убиты.
Открыв военные действия против русской Экспедиции, башкиры положили начало новому восстанию, самому кровопролитному и самому упорному из всех восстаний этого народа, которое продолжалось с 1735 до 1740 года.
Получив сведение о нападении башкир на отряд Чирикова, Кирилов выслал к нему на помощь отряд. Но отряд этот под давлением башкир вернулся обратно. Кирилов усилил его еще одной сотней казаков и выслал снова, после чего ему удалось соединиться с Вологодским полком.
Соединив отряды, Экспедиция продолжала свое движение к устью р. Орь.
Еще будучи в пути Кирилов получил известие, что Сибирский продовольственный транспорт окружен башкирами и находится в осаде, в 30 в.не доходя Верхне-Яицкой пристани. Задержание продовольственного транспорта поставило Экспедицию Кирилова в крайне тяжелое положение, т. к. у него уже ощущался недостаток в продовольствии.
Закладка гор. Оренбурга. Продолжение борьбы с башкирами
6-го августа Кирилов достиг р. Яика при устье р Орь. Здесь к нему явились представители казакского народа, при помощи которых ему удалось заготовить запасы продовольственного скота для Экспедиции и таким образом предотвратить голод в отряде до прибытия транспорта из Сибири, навстречу которому он выслал особый отряд.
15-го августа Кирилов заложил гор. Оренбург, который должен был стать оплотом русского господства во вновь присоединенной окраине.