В мае Неплюев отправил в Правительствующий Сенат проект-предложение о новой застройке Оренбурга и, не дождавшись ответа, начал вести подготовку к ней. Осенью из Петербурга пришел ответ: указ Сената от 21 октября 1742 года санкционировал застройку города близ места, где встречался Яик с Сакмарой.
Всю зиму шли подготовительные работы. Сотни ремесленников и ссыльных людей стекались к месту будущей стройки. Обозами везли из Башкирии древесину, с яицких берегов и орских угорий — камень, гальку, яшму. С рудных заводов — листовое железо, литье.
19 апреля 1743 года при торжественном молебствии и артиллерийском салюте город был заложен в третий раз — на том месте, где он стоит поныне.
Стройка велась ускоренно, под круглосуточным воинским караулом. Окрест рыскали отряды киргиз-кайсаков, нападали на русские поселения и обозы, захватывали в плен женщин и детей, находившихся без охранения на сенокосе или жатве хлебов. Разбойничьим налетам подверглись крепости Сорочинская и Новосергиевская, Илецкий городок.
Неплюев, крайне занятый стройкой, вынужден был искать встречи с Абул-Хаиром, с которым он еще не успел познакомиться. Он направил к хану посла с дарами и пригласил в гости. При встрече Неплюев потребовал от Абул-Хаира объяснить вероломства, чинимые его людьми, попросил подтвердить подданство новой императрице Елизавете Петровне, дочери Петра Великого. Хан присягнул на Коране и, увешанный дорогими подарками, удалился в казахские степи.
Осенью на строителей навалилась цинга, из 1350 человек 630 умерло. Несмотря на трудности и замешательства, Оренбург спешно строился, и уже до заморозков новопоселенцы и воинский гарнизон были введены в теплые дома и казармы. Все лето до октября Неплюев наравне со всеми жил в землянке, только своей 12-летней дочери Анне выделил кибитку. Он лично руководил всем строительством, наказывал нерадивых, жаловал умелых, корректировал проект, не изменяя его основы. По тому времени Оренбург раскинулся на довольно внушительной территории. Ширина города равнялась 570 саженям (более километра), а длина — 677 саженям. Город окружили рвом и валом с десятью каменными бастионами по углам. Наружная часть вала была облицована плитным камнем. На бастионах стояли пушечные батареи. Вооруженная стража охраняла четверо городских ворот: Сакмарские, Яицкие, Губернские и Орские.
Уже в сентябре 1747 года в Оренбурге насчитывалось 837 дворов, четыре церкви, гауптвахта, аптека, госпиталь, пороховые склады, провиантские и соляные магазины, таможня, 44 лавки в каменном Гостином дворе и 131 лавка на Меновом.
