10 апреля 1735 г. Кирилов выступил со своим отрядом в поход на р. Орь и, отойдя верст десять от Уфы, расположился лагерем на р. Чесноковке. Прождав здесь около двух месяцев напрасно Вологодский полк, он 15 июня двинулся дальше, имея в своем распоряжении 15 рот регулярных войск, 350 казаков, 600 мещеряков, 100 башкир и, кроме того, обоз с провиантом и артеллерийскими орудиями, предназначавшимися для будущей Оренбургской крепости, и в том числе 252 5-фунтовых медных пушек, две пудовые гаубицы и две 32-фунтовые медные мортиры.
Незадолго до выступления из лагеря к Кирилову явились башкирские послы и предложили ему отказаться от похода на р. Орь и сооружения там города. В случае невыполнения этого требования они грозили всеобщим восстанием. Кирилов, не обратив внимания на угрозы, продолжал продвигаться по намеченному маршруту.
Однако вскоре он вынужден был остановиться и выслать на помощь догонявшим его ротам Вологодского полка под командованием подполковника Чирикова, подвергшимся нападению башкир, особый отряд, который помог им выйти из окружения и соединиться с отрядом Кирилова. В своем доношении в Петербург Кирилов постарался представить все происшедшее как незначительное столкновение, случившееся только потому, что подполковник Чириков допустил оплошность, пренебрег данной ему инструкцией и не принял необходимых мер предосторожности. Однако, опасаясь, чтобы это происшествие не повлияло на дальнейшую судьбу возглавляемой им экспедиции, вслед за этим доношением он отправил письмо всемогущему временщику Бирону. Кирилов просил Бирона оказать ему помощь и содействие в том случае, если в Петербурге в правительственных кругах «новозачатое дело» будет признано «отчаянным и неимоверным» и если будет решено из-за этого случайного происшествия отказаться от начинания, предпринятого к великой славе и пользе государства.
Отправив письмо, И. К. Кирилов продолжал настойчиво и неуклонно двигаться к намеченной цели. К трудностям и опасностям, с которыми было связано это продвижение, вскоре, по словам П. И. Рычкова, прибавился «внутренний неприятель» — голод, так как взятый из Уфы провиант вследствие непредвиденной задержки из-за нападения башкир кончился еще до прибытия на р. Орь [39, стр. 131]. 6 августа 1735 г. Кирилов прибыл к устью р. Ори.
15 августа он заложил крепость «о девяти бастионах» с «цитаделью малою» и на другой день отправил императрице поздравление с приобретением Новой России, которая, как писал он, по своим природным богатствам будет иметь не меньшее значение, нежели открытые европейскимим державами новые, прославленные металлами и минералами земли, так как по дороге к р. Ори и на месте будущего города он нашел признаки богатых медных и серебряных месторождений, а также камни — порфир, яшму и мрамор [29, стр. 497—498]. 30 августа постройка крепости была закончена и в нее были введены гарнизон и артиллерия. 31 августа при троекратном салюте из пушек был заложен город Оренбург.
6 сентября И. К. Кирилов двинулся в обратный путь, имея при себе драгунские роты Вологодского полка и яицких, сакмарских и уфимских казаков.
Между тем вспыхнувшее восстание росло и ширилось. К феодалам Ногайской, дороги, поднявшим восстание, присоединились феодалы Сибирской и Казанской дорог. Используя в своих классовых интересах недовольство трудящихся башкир произволом царских чиновников, башкирские феодалы постарались «придать начавшейся борьбе антирусский, антинародный характер» [34, стр. 171—172]. Чтобы заставить трудящихся башкир принять участие в движении, они разжигали в них ненависть к русским, и если это не помогало, то прибегали к прямому насилию. Тем не менее значительная часть населения Башкирии не только отказалась примкнуть к восставшим, но и вступила в борьбу с ними. За время пребывания И. К. Кирилова в Оренбурге башкиры в количестве более тысячи человек пытались осадить Мензелинск, напали и разорили Табынск, Билярск, Заинек, Старошешминск, ограбили и сожгли в Уфимском уезде деревни мишарей и башкир, отказавшихся примкнуть к восстанию.
Обратный путь Кирилова в Уфу был сопряжен с большими трудностями и опасностями. В 130 верстах от Уфы он подвергся нападению башкир под предводительством Кильмяка и Акая. Отбив нападавших с большими для них потерями, Кирилов отправил отряд под командой полковника Анненкова к Табынску для преследования скрывавшихся на pp. Дёме и Уршаке башкир, сам же во главе оставшегося под его командой отряда благополучно вернулся в Уфу.
Встревоженное первыми известиями о начавшихся в Башкирии волнениях, царское правительство направило в Башкирию генерал-лейтенанта А. И. Румянцева, уполномочив его действовать главным образом уговорами и увещеваниями и лишь в крайнем случае, если уже уговоры не помогут, то употребить оружие [47, стр. 328]. Кирилову было предписано во всем повиноваться Румянцеву и выполнять все его распоряжения, касающиеся восстания.
