Но не смотря на такое симпатичное желание, комитету не пришлось тотчас приступить к работам — место в размере 25 тыс. кв. саж. было отведено думою там, где теперь Тополевый садик и главная причина была в том, что комитет имел только эскиз проекта и не знал сколько же стоит предполагаемая постройка. По предварительным исчислениям оказалось, что необходима сумма около 700 т. р.
Сумма эта была слишком значительная; не забудем, что у комитета было всего около 80 т. рублей и комитету вместо работ пришлось позаботиться о проекте. Одно время было намерение воспользоваться уже готовым и разработанным проектом, по которому исполнен нижегородский ярмарочный собор, стоивший 454019 руб. Благодаря любезности нижегородского головы комитета, получил подробные сметы и чертежи — но нижегородский храм оказался и дорогим и великим по размерам на 3300 человек — опять комитет остался без проекта. В этом искании подходящего проекта прошло четыре года когда в 1885 году на помощь комитету пришел Оренбургский губернатор Н. А. Маслаковец, который предложил воспользоваться услугами бывшего в Оренбурге академика Ященко. Комитет согласился на это предложение, в мае 1885 года Ященко представил эскиз, эскиз был одобрен, Ященко приступил к детальной разработке проекта и 23 января 1886 г. был Высочайше утвержден составленный Ященко проект на сумму постройки в 213400 р. без стоимости крестов, иконостасов, стенной живописи, тротуаров и церковной ограды.
Первоначальное место на Караван Саранской площади признано было неудобным и дума отвела новое место, на Сакмарской площади, где собор в настоящее время и поставлен.
8 сентября 1886 года после литургии архиерей Макарий с крестным ходом опустился по земляному откосу в глубь разработанного места для постройки храма на площадь закладки его, углубленную до 10 1/2 аршин и совершил закладку храма при весьма торжественной обстановке. Земляные высокие стены, обрамляющие эту площадь, обнесены были перилами, украшенными ветвями дерев и флагами, для входа были устроены высокие ворота с русской резьбою красиво декорированные зеленью и флагами. Среди несметных масс народа были расположены войска и три военных оркестра.
В этот же день в зале городской думы состоялся общественный по подписке обед, на котором было собрано свыше 30 т. руб.
Дальнейшие работы следовали так: в 1887 году был выложен весь бут и обложен кирпичом подвальный этаж, в 1888 — выложен цоколь; с 1889 г. по 1893 г. включительно производилась кирпичная кладка по ярусам, в 1893 г. собор был покрыт железом, в том же году начаты и в 1894 году окончены штукатурные работы сводов и внутренних стен собора.
В 1893 году пред окончанием постройки собора вчерне, когда уже денежные средства значительно истощились и явились опасения, что отделка храма и освящение его отдаляется на продолжительное время, пришла на помощь с щедрым пожертвованием в 30 т. руб. вдова Оренбургского купца М. Л. Иванова. Пожертвованная ею сумма ушла на устройство иконостаса, на писание икон и на колокола. Для отливки колоколов был вызван в Оренбург особый мастер, колокола были отлиты в 723 пуд. 32 ф. и 302 п. 33 ф. и 27 ноября и 4 декабря 1894 г. подняты на колокольню, 9 же декабря 1894 года произошло поднятие и большого креста. Не останавливались одновременно с этим и другие работы внутри храма: устроена лестница, полы, установлены иконостасы и 19 октября 1895 года было произведено освящение храма.
Общая сумма, истраченная на постройку, превышает 400 т. руб.
Оренбургский собор построен в византийском стиле на подобие храма Св. Софии в Константинополе, с высящимся по средине обширным куполом, по бокам которого с трех сторон облегают три полукупола, а между ними красиво выступают снаружи четыре колоколенки. Высоко поднимаясь над городом, собор как бы парит над ним, а его массивность и грандиозность оставляют в зрителе вместе с красотой вида и гармонией частей впечатление силы и величия постройки. Внутри собор расписан в стиле собора Св. Марка в Венеции. При обилии дневного света, льющегося со всех сторон из больших окон, а также при освещении собора вечером электричеством, внутренность его ныне имеет необычайно красивый и величественный вид.
В соборе есть несколько образов, исполненных художником Вл. Маковским.