Обширную территорию на юго-востоке Российской империи часто называли «Диким полем», малопригодным для жизни и не привлекательным для промышленного освоения. 

В скором времени Иван Кириллович Кирилов разработал проект «Изъяснение о киргиз-кайсацкой и каракалпакской ордах», в котором обосновал необходимость организации специальной экспедиции. Учёный остановился на описании казахских и каракалпакских степей, начиная от природных условий, полезных ископаемых и заканчивая изучением торговых путей и перспектив налаживания торгово-экономических связей. Кирилов предлагал построить в устье реки Орь город-крепость и цепь укреплений по Яику и другим рекам — пограничную линию.

15 (26) августа 1735 года на левом берегу реки Яик восточнее места впадения в неё реки Орь на границе Бурзянской, Кипчакской волостей Уфимской провинции и казахских степей была заложена крепость Оренбург, как будущий центр Оренбургской губернии.

В декабре 1735 года Кирилов, отправившийся в Петербург для представления своих планов освоения Башкирии, убедил императрицу Анну Иоанновну утвердить план о подавлении башкирских восстаний силами казаков. Причиной необходимости принятия жёстких мер послужили неоднократные набеги башкир на строящиеся города, препятствовавшие развитию губернии и приводившие к многочисленным жертвам среди русских переселенцев. Этого плана Кирилов придерживался вплоть до своей смерти.

Сильные разливы рек заставили начать в 1739 году подготовку к строительству нового города с прежним названием ниже по течению Яика. Однако строительство города так и не началось: выбранное место на Красной горе безлесное, каменистое и удалённое от реки, также оказалось неподходящим для строительства.

19 (30) апреля 1743 года Оренбург был заложен в третий раз, на месте бывшей Бердской крепости, на удалении более чем в 200 километров от первоначальной локации.

Крепость, в течение некоторого времени известная под именем «первого Оренбурга», была сохранена, а с августа 1741 года стала именоваться Орской (указ «прежний Оренбург именовать Орская крепость» вышел 20 августа 1739 года) и со временем стала главной крепостью Орской дистанции Оренбургской линии, в её подчинение входили пять других крепостей и девять редутов.

В 1738 году в полуверсте от Орской крепости новым начальником Оренбургской экспедиции Василием Никитичем Татищевым был построен меновой двор (на его месте сейчас находится рынок Старого города). С 1746 года крепость начинает терять торговое значение в связи с развитием оренбургского менового двора, однако торговые пути на Хиву и Бухару, как и маршрут из Зауралья в Оренбург, продолжали проходить через неё.

Во время пугачёвского восстания крепость оказалась единственной уцелевшей в Орской дистанции, и даже не подвергавшейся приступам.