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