По прибытии в крепость Бердскую, которая была построена на месте нынешнего Оренбурга, Неплюев решил основать новый город здесь.
— «Из всех мест по р. Яику, — доносил Неплюев кабинет-министрам, — тут хлебопашество лучше устроено, а пахотной земли, сенных покосов, рыбных озер, одним словом, всего того, что при великом городе довольствию и жительству людскому на всегдашнее время нужно, довольно».
И, действительно, в окрестностях избранного места имелись большие запасы строительного камня, необходимого для постройки города, по реке Сакмаре сюда можно было сплавлять лес из Башкирии. В смысле путей сообщения нового краевого центра с Россией, он находился в лучшем положении, нежели Орск. Из Оренбурга было удобно управлять Казакской ордой, т.к. большая часть казаков кочевала летом по р. Илеку.
В силу этих соображений, 19 апреля 1743 г. Неплюев заложил гор. Оренбург на настоящем его месте.
В плане, составленном инженером Штокманом, Оренбург представлял собою многоугольник об 11 полигонах, 10 бастионах и 2-х полу-бастионах. Город был обнесен валом и рвом. Высота вала достигала до 12 футов, ширина рва — 5 сажен, а глубина 12 футов. Длина крепости занимала 677 саж., а ширина — 570 саж. Общая окружность обвода укрепления равнялась 5 в. 192 саж. В город вели 4 ворот: на востоке — Орские ворота, на западе — Чернореченские и Уральские и на севере — Сакмарские.
Для постройки нового города были наряжены башкиры, тептяри и уфимские казаки. Работы производились при чрезвычайно тяжелых условиях в смысле продовольствия. За время работ заболело цингой 1350 рабочих, из которых умерло 631 человек.
В течение лета в 1743 г. город был построен. Здесь были выстроены дома не только для правительственных учреждений, но и для частных лиц, которым сдавались на чрезвычайно выгодных условиях. Неплюев разослал приглашения в города Уфу, Самару и другие места, предлагая купцам поселиться в новом городе. Первыми для заселения нового города явились казанские татары, которые уже имели торговые связи с казаками.
В 1745 году казанский татарин Сеит Хаялин с товарищами, в числе 300 дворов, испросил разрешение у Неплюева на постройку Сеитовской татарской слободы между Оренбургом и Сакмарским городком. Сеит обязался завести здесь хлебопашество и даже хлопковые плантации, но опыты с последними не удались и татары занялись исключительно торговлей с казаками. В 1784 г. сеитовские татары получили привилегии торговых татар.
Построив Оренбург, Неплюев позаботился наладить сообщение нового центра с городами Уфой и Казанью, для чего по направлению к Уфе был устроен почтовый тракт, так называемая Новая Московская дорога. Так как башкирское население по тракту было очень редко, то Неплюев устроил здесь ямские слободы, заселив их казанскими татарами. В 50-х годах XVIII в. по Ново-Московскому тракту уже насчитывалось 4720 душ населения, половина из них были татары, содержавшие почтовую гоньбу, за которую они освобождались от воинской повинности.