30 августа в крепость ввели солдатскую команду, а на следующее утро установили артиллерию. В тот же день, 31 августа, торжественно заложили «настоящий Оренбург о девяти бастионах... при выстрелах из тридцати одной пушки», — пишет П. И. Рычков, состоявший бухгалтером при экспедиции.
В церемонии закладки принимали участие киргиз-кайсаки Младшего и Старшего жузов, башкиры. Были и купцы из Ташкента. И. К. Кирилов пригласил азиатских и русских купцов на следующий год на торг в Оренбург. Таким образом, сразу выявились обе основные функции города: быть оплотом и центром экономического и политического общения с Востоком. Расположение города на левом берегу Яика подчеркивало, что крепость должна служить защитой киргиз-кайсакам.
Постройку девятибастионного, города-крепости отложили до следующего года, но и тогда работы начать не смогли, так как силы были отвлечены на подавление восстания в Башкирии. Не приступили к строительству и через год, потому что 14 апреля 1737 года И. К. Кирилов умер, а новый начальник В. Н. Татищев не одобрил выбор расположения главного города края. Место было слишком удалено от других городов, отделялось горами, что затрудняло коммуникации. Сама площадка, где заложили город, затапливалась в половодье. Недостатком было и отсутствие леса. Поскольку город был только заложен, можно было основать его на другом месте. Поэтому В. Н. Татищев отправил на осмотр мест инженер-майора Ратиславского, послав его в Сакмарск и на урочище Красной горы, о котором ему сообщили, что оно удобно для постройки города.
Летом 1738 года В. Н. Татищев сам прибыл к Красной горе. Он выбрал место на некотором расстоянии к востоку от горы. Часть его теперь занимает село Красногор.
В начале 1739 года В. Н. Татищев отправился в Петербург, где подал в кабинет обстоятельные представления по устройству края. Среди них одним из главных было предложение строить Оренбург у Красной горы. С Татищевым согласились, но ему не пришлось осуществить свои проекты. На него поступили доносы, по которым он обвинялся в злоупотреблениях. В. Н. Татищев был отстранен от должности, и на его место назначили генерал-лейтенанта князя В. А. Урусова.
20 августа 1739 года вышел указ, где говорилось: «Город Оренбург строить на изысканном месте... при Красной горе... прежний Оренбург именовать Орская крепость».
Прибыв в Самару, князь Урусов сразу стал принимать меры к тому, чтобы летом 1740 года начать строительство Оренбурга. Однако этому помешало восстание в Башкирии, которое по указу из военной коллегии ему надлежало подавить, что он сделал с чрезвычайной жестокостью. В одном Сакмарском городке, где производилось следствие над частью повстанцев, было казнено 170 человек, более трехсот человек наказали кнутом и «урезыванием носов и ушей для публичного знака». Происходило это уже в последних числах сентября и для строительства города времени не оставалось.