Наконец 1 августа 1741 года город Оренбург был заложен. Однако начатые было работы вскоре приостановились из-за незатухавших споров о месте строительства — по косогору или на ровной площадке. В. А. Урусова уже не было в живых, он умер еще за 10 дней до закладки города. Только в феврале 1742 года назначили нового главного командира. До этого Оренбургскую комиссию временно возглавлял начальник башкирской комиссии генерал-лейтенант Соймонов, которому ряд обстоятельств мешал разобраться в споре.
Новый начальник комиссии И. И. Неплюев прибыл в Самару 26 апреля 1742 года и в первую очередь занялся вопросом строительства нового города. Вникая в существо спора между строителями, он рассмотрел планы карты не только у Красной горы, но и других мест. Изучив все материалы, И. И. Неплюев пришел к выводу, что город лучше было бы строить не у Красной горы, а недалеко от впадения в Яик реки Сакмары Место это расположено ближе к российским хлебным местам и находится в середине линий новопостроенных крепостей. Кроме того, здесь было больше воды и леса. Свои соображения И. И. Неплюев сообщил правительствующему Сенату.
В этом районе город можно было строить у Черноречья или к востоку от устья Сакмары, где уже имелась основанная еще Кириловым небольшая Бердская крепость, отчего все место называлось Бердск. Окончательно решение о строительстве на новом месте Неплюев принял по прибытии в Орскую крепость, собрав на совет обер-офицеров. Вскоре, 28 июля, в Петербург с планом и проектом был отправлен капитан Лука Галофеев. Так окончилось строительство Оренбурга при Красной горе, где, по-видимому, произвели только разбивку местности под застройку да сделали небольшой участок рва и вала. Направление улиц села Красногор, занимающего сейчас юго-западную часть территории непостроенного города, позволяет предположить, что при застройке частично использовалась старая разметка.
Проект был утвержден императрицей Елизаветой 15 октября 1742 года резолюцией на докладе Сената, где в резюме говорится: «При урочище Красной горы... города Оренбурга строить не надлежит, а... надлежит оный строить... при Бердской крепости». Последнюю следовало перенести на новое место.
Весной 1743 года из Самары к месту строительства выступила команда, которую возглавлял генерал-майор фон Штокман, и 19 апреля того же года Оренбург был торжественно заложен на нынешнем месте. Эту дату и следует считать днем основания нашего города.
В процессе строительства были сделаны отступления от утвержденного проекта. Сразу же крепостную ограду стали строить не на окружности, а на овале, отступив на западе от склона к пойме, очевидно, для создания большего простреливаемого пространства перед крепостью, а на востоке отошли ради симметрии. Позже и Меновой двор построили на Бухарской стороне, а не перед крепостной оградой. В первый строительный сезон сумели насыпать вал вокруг всего города, но значительно меньшего объема, чем предусматривалось по проекту, однако, как пишет П. И. Рычков, «к тогдашнему защищению весьма довольный».