Там, где сначала намечали строить собор, построили сперва часовню. В ней собирали пожертвования. Она стоит напротив Тополевого сада, ее до сих пор зовут «Собирика». Открыли ее в 1875 г. и за двадцать лет собрали почти 58000 рублей. Строительство стоило более 400 тысяч и началось лишь в 1886 г. Задержка вызвана пожарным бедствием 1879 г., после которого пришлось много строить и восстанавливать, и поисками подходящего проекта.
На лучший проект объявили конкурс. Он проходил при Императорской Академии Художеств. Наиболее удачными признали два проекта — архитектора Шретера и художника Леонова. Но у первого проигрывал внешний вид по сравнению с проектом Леонова. Зато у последнего неудачным оказалось решение плана. Шретеру предложили переработать проект, решив фасады в духе леоновского проекта. Эскизный проект был признан годным в октябре 1879 г., но по предварительным подсчетам строительство обошлось бы тысяч в 700. Таких денег у города не было. Думали уж построить собор по готовому проекту Нижегородского собора. Но он тоже обошелся бы дороговато: в Нижнем потратили 451015 рублей, к тому же собор был слишком велик. Строительный комитет потратил еще несколько лет на поиски подходящего проекта. Помог в этом деле бывший Оренбургский губернатор Николай Алексеевич Маслоковец; генерал-губернаторство было упразднено в 1881 г., и Крыжановского уже не было. Маслоковец предложил в 1885 г. обратиться к академику архитектору Ященко, который тогда был в Оренбурге. Тот согласился и уже в мае представил эскиз, его одобрили, а 23 января 1886 г. полностью завершенный проект был Высочайше утвержден. Для этого проекта и выбрали место, где теперь стоит собор.
Сразу же весной начались земляные работы, и 8 сентября 1886 г. произошла торжественная закладка храма. Все место обнесли перилами, украсили их ветвями и флагами. Входные ворота с русской резьбою тоже украсили зеленью и флагами. После литургии архиерей Макарий с крестным ходом спустился по земляному откосу и совершил закладку храма. Присутствовали при сем масса народа, войска и три военных оркестра.
Кладку закончили в 1893 г. На следующий год закончили штукатурные работы и отлили колокола. Главный колокол весит 723 пуда 32 фунта. Поднимали колокола в ноябре и декабре того же 1894 года. 9 декабря подняли и большой крест.
В 1893 году стали опасаться, что не хватит средств на отделку и освящение храма придется откладывать. Тут вдова купца М. Л. Иванова пожертвовала 30 тысяч. Эта сумма ушла на иконостас, писание икон, колокола.
