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