Осенью 1734 г. И.К.Кириллов прибывает в Уфу, где усиленно занимается подготовкой похода на р.Орь. Для доставки хлеба из близлежащих зауральских слобод к месту будущего города Оренбурга в феврале 1735 г. в верховьях Яика закладывается Верхнеяицкая пристань (впоследствии — крепость), заселенная двумя ротами солдат Уфимского гарнизонного полка и уфимскими казаками. К отряду И.К.Кириллова были прикомандированы 150 уфимских, 200 самарских и 150 башкирских казаков. Причем, по поводу последних в собственноручной инструкции императрицы Анны Иоанновны, составленной в мае 1734 г., Кириллову предписывалось: Как регулярным, так и нерегулярным русским служилым людям, когда случай и поспешность позовет в строение города или магазинов и других казенных работ, то их употреблять, давая заработные деньги по рассмотрению работ. А башкирцев отнюдь в работу не наряжать и тем их от охоты к службе не озлоблять, ибо они служат и служить имеют без жалования и на своих лошадях, и со своим ружьем (выделено нами — В.И., С.Ч.)». Кроме того, Кириллову предписывалось перевести в новый город самарских и яицких казаков «сколько возможно». В результате самарские казаки были переведены в Оренбург в полном составе, а яицких — 500 человек «охотников». По дороге Кириллов приказал укрепить крепость Табынск с его соляными варницами. Там были обновлены вал и ров, поставлен палисад, установлены пушки и размещен гарнизон, состоявший из полуроты солдат и сотни казаков.
Город-крепость Оренбург был заложен 15 августа 1735 г. в устье р.Орь (левый приток р.Урал). Первоначально это была небольшая крепость «о четырех бастионах с цитаделью малою на горе Преображенской».
Присутствие крупного воинского контингента, строительство новых укреплений, а главным образом — непродуманные действия правительства по массовому изъятию башкирских земель и передачи их новопоселенцам* привели к тому, что башкиры, которые еще в 1734 г. сотрудничали с русской администрацией и даже помогали в поисках места под новый город и в возведении более мелких укреплений, летом 1735 г. подняли восстание. В течение июля-августа 1735 г. восстание охватило всю приуральскую Башкирию. Восставшие перехватывали обозы с провиантом и припасами, следовавшие к Оренбургу, разгромили Верхнеяицкую пристань и другие укрепления, сжигали русские поселения и разгоняли или убивали их жителей. 19 июня 1735 г. на 160-й версте от Уфы, возле горы Зирган отрядом повстанцев под предводительством Кильмяка Нурушева был остановлен и чуть не уничтожен Вологодский драгунский полк, в составе которого на соединение с корпусом И.А.Кириллова шли несколько десятков уфимских дворян и казаков. В феврале 1736 г. в 47 верстах от Уфы повстанцы окружили и полностью перебили отряд уфимских казаков атамана Кадомцева.
В 1736 г. на подавление восстания в Башкирию были брошены значительные воинские силы под командованием генерал-лейтенанта А.И.Румянцева. В их составе находились 3000 волжских калмыков, 1000 донских и 2000 яицких казаков, а также отряды тептярей, мещеряков и нагайбаков, поддержавших действия царских войск. В мае 1736 г. восставшие потерпели несколько поражений, но не сложили оружия.
На фоне развернувшейся партизанской войны башкир И.К.Кириллов продолжал выполнять планы Оренбургской экспедиции. Была восстановлена Верхнеяицкая пристань, ставшая ввиду ее стратегического значения крепостью. Рядом с ней была заложена новая крепость — Карагайская. Заново укрепляется Табынск. 13 апреля 1736 г. Кириллов издает указ, предписывавший комиссару И.Д.Утятникову привести Табынск в надлежащее состояние, чтобы в нем можно было поселить две роты драгун и 300 казаков. Казачий контингент крепости в основном пополнялся за счет татар и мишарей, добровольно верставшихся в казаки. По данным историка Р.Г.Букановой, в 1737 г. гарнизон Табынской крепости состоял из 600 драгун, 300 яицких казаков, 1500 «новоприборных» казаков* и 400 солдат Казанского гарнизонного батальона. На север от Уфы, по Сибирской дороге строятся крепости Красноуфимская и Ельдятская, в которых было поселено до 300 служилых казаков. Тогда же, по указанию Кириллова, деревня Нагайбацкая у западных пределов Башкирии была укреплена и обращена в крепость. Жившие в ней нагайбаки обращены в христианство, освобождены от уплаты оброка за землю тамошним башкирам и поверстаны в казаки. Служить они обязались за свой кошт и только при командировках от своих домов далее 100 верст казаки-нагайбаки получали от правительства жалованье, провиант и фураж.
Тяжелая военная обстановка в крае заставила правительство вспомнить о проекте главного начальника казанских и сибирских заводов В.Н.Татищева, предложенном им в марте 1735 г. По этому плану предполагалось, для обеспечения спокойствия в крае и охраны русских поселенцев, построить пять крепостей в верховьях рек Яик, Уй, Теча и на озерах Чебаркуль и Аргази. В течение 1736-1738 гг. были построены крепости Чебаркульская, Миасская, Кизилташская, Еткульская и Карагайская. Обновлены и усилены оборонительные сооружения Челябинской крепости. Одновременно строится цепь укреплений по рекам Самара (Красносамарская, Борская, Елшанская, Бузулукская, Тоцкая, Сорочинская) и Яик (Бердская, Татищевская**, Чернореченская, Верхнеозерная, Губерлинская). В сторону укреплений Яицкого Казачьего Войска вниз по течению р.Яик возводятся форпосты Илекский, Кинделинский, Иртекский, Рубежный, Генварцевский, Кирсановский. Новые крепости обносились рвами и валом, а также рогатками, тыном и двойными плетнями с глиной в промежутках или укреплялись другими способами на усмотрение ближайшего начальства. Крепости снабжались пушками, комплектовались гарнизонами из драгун и пехотных солдат.
В апреле 1737 г. в разгар своей деятельности на Южном Урале умер начальник Оренбургской экспедиции и на эту должность, вполне логично, был назначен В.Н.Татищев. Он продолжил административную политику своего предшественника, заложив еще две крепости: Переволоцкую и Новосергиевскую. Заручившись поддержкой хана Младшего Жуза Абулхаира, В.Н.Татищев в 1738 г. отправляет из Оренбурга первый торговый караван в Среднюю Азию.
Найдя неудачным выбранное Кирилловым место под г.Оренбург (удаленность от русских поселений, разливы рек Яика и Ори, подмывающих постройки, отсутствие строительных материалов), В.Н.Татищев предложил перенести столицу края на 150 верст ниже по течению Яика, в урочище Красная гора. Правительственным указом от 20 августа 1739 г. это предложение было принято. Предписывалось строить г.Оренбург на новом месте, а прежнюю крепость называть теперь Орской.