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