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