Осмотрев город и места по реке Яику, Татищев пришел к выводу о необходимости перенесения Оренбурга в урочище Красная гора (на месте современного села Красногор Саракташского района) и возбудил об этом ходатайство. Основанием для перенесения он указывал: отдаленность Оренбурга от «российских городов», трудность и дальность дороги для русских купцов, непригодность окрестных земель для хлебопашества вследствие песчаной почвы, затопляемость города в весеннее время и отсутствие поблизости лесов.
Ходатайство Татищева было удовлетворено. Указом от 20 августа 1739 года разрешалось «город Оренбург строить на изысканном месте вновь при Красной горе..., а прежний Оренбург именовать Орская крепость...»
В начале августа 1741 года Оренбург был снова заложен в урочище Красная гора. Однако работы шли очень медленно, а затем совершенно прекратились.
В начале 1742 года начальником Оренбургской комиссии был назначен тайный советник И. И. Неплюев, видный политический деятель, бывший посол в Турции, попавший в немилость. Он ознакомился с крепостями, построенными по Самаре, Яику, осмотрел урочище Красная гора и пришел к выводу, что выбранное Татищевым место для строительства города имеет много неудобств. По мнению Неплюева и сопровождавших его офицеров, наиболее подходящим местом для Оренбурга являлся район устья реки Сакмары (территория современного города Оренбурга), где в то время стояла небольшая Бердская крепость.
Местоположение Бердской крепости действительно имело целый ряд преимуществ. Она находилась почти в середине вновь построенной военной линии по Яику и Самаре, была ближе к центру России, удобнее для русских купцов. В нескольких километрах находилось устье реки Сакмары. по которой можно было доставлять из Башкирии строевой лес. Кругом расстилались обширные ковыльные степи с тучными черноземными почвами. Недаром это место с давних пор привлекало русских поселенцев.
П. И. Рычков отмечает, что это «место весьма способное и всеми к жительству надлежащими способностями довольное».
Летом 1742 года Неплюев представил правительству проект о строительстве города на месте Бердской крепости. Указом от 15 октября 1742 года проект Неплюева был утвержден. Название города оставалось прежнее — Оренбург.
19 апреля 1743 года после торжественной церемонии и под грохот артиллерийского салюта город Оренбург был заложен на его теперешнем месте. Город, заложенный в урочище Красная гора, стал именоваться Красногорской крепостью.
Оренбург был заложен как крепость. Авторами первого проекта были русские военные инженеры капитан Галафеев и прапорщик Тельной. Город был обнесен высоким земляным валом с 10 бастионами и 2 полубастионами. Один из бастионов получил название Галафеевский. С внешней стороны вал опоясывался глубоким рвом.