Через 9 лет деревянная церковь заметно обветшала и на расположенном против нее огромном пустынном плацу, 16 апреля 1752 года, Императрица Елизавета Петровна повелевает строить каменную полковую церковь. Составить смету и план храма было поручено состоявшему при Адмиралтействе архитектору Савве Ивановичу Чевакинскому. Хотя смета была готова уже к маю, летом, из-за отсутствия материалов, к работе не приступили, а осенью случилось наводнение, затопившее место постройки храма. Чтобы избежать впредь подобной опасности, Адмиралтейская коллегия определила поднять уровень пола храма на 3 аршина (более двух метров). Архитектор согласился с доводами комиссии и для сохранения строгих пропорций здания несколько увеличил как высоту, так и ширину храма.
По окончании земляных, свайных и бутовых работ, 15 июля 1753 года Преосвященным архиепископом Санкт-Петербургским и Шлиссельбургским Сильвестром была совершена закладка каменного
храма во имя св. Николая Чудотворца.
Постройка начатого храма подвигалась быстро, весной и летом 1754 года был сделан первый этаж, осенью окончена кладка второго этажа. Материалы для крыши и куполов были предоставлены П. А. Демидовым. В 1758 году были произведены работы по золочению глав и куполов храма. Иконостас храма был устроен из высушенных липовых досок и кленовых кряжей С. Никулиным и подмастерьем И. Кунаевым. Золочение иконостаса производил искуснейший московский золотарь Семен Золотой. Образа для иконостасов были написаны в 1755—60 годах для верхнего храма Федотом Колокольниковым, а для нижнего — братом его Миною по реестру святых образов, назначенных архитектором Чевакинским к написанию.
Главный алтарь нижнего (теплого) храма во имя св. Николая Чудотворца был священ 5 декабря 1760 года, в царствование Императрицы Елизаветы Петровны, о чем свидетельствует памятная мраморная доска, установленная в нижнем храме.
Всего в соборе четыре престола: три в нижней церкви: средний во имя св. Николая Чудотворца, правый — во имя Усекновения главы Иоанна Предтечи, левый — во имя святителя Димитрия Ростовского; и один в верхней — во имя Богоявления Господня.
Верхний (холодный) храм во имя Богоявления Господня был освящен архиепископом С.-Петербургским Вениамином 20 июля 1762 года в присутствии Императрицы Екатерины Второй, изустно повелевшей впредь именовать новопостроенную морскую полковую церковь собором.
В 1770-х годах в храме в Высочайшем присутствии отправлялись благодарственные молебны по случаю морских побед в русско-турецкой войне. Императрицей Екатериной 11 в храме были пожертвованы 10 живописных образов с ликами тех святых, в дни памяти которых были одержаны победы над турецким и шведским флотами в 1770, 1789 и 1790 годах.
В 1756 году, к западу от храма, на достаточном удалении, была выстроена четырехъярусная колокольня, необычайно изящная и легкая по архитектуре. На колокольне установлены колокола для церковного звона и боевые часы с курантами, отбивающие каждую четверть часа. Колокола, используемые для боя часов, были отлиты в Москве, на заводе Мозжухина.
В 1780—87 годах с собором был прорыт Никольский (позже — Крюков) канал, и здание колокольни оказалось стоящим на набережной, создав неповторимый облик этого тихого уголка города.
Были при храме библиотека и церковный архив. Духовенство и клирики храма активно занимались благотворительной деятельностью. С 1870 года при соборе действовало «Общество вспоможения приходским бедным», содержавшее детский приют и богадельню.
После 1917 года храм не закрывался и дошел до нас в первозданном виде. Николо-Богоявленский собор стал кафедральным с 1941 года, когда в дни 900-дневной блокады его избрал своей резиденцией митрополит Ленинградский и Новгородский Алексий (Симанский), служивший в храме с 1941 по 1944 гг., до момента своего восшествия на Патриарший престол. Митрополит Алексий и священнослужители Николо-Богоявленского собора были награждены медалью «За оборону Ленинграда».
В 1960 годах настоятелем храма был протоиерей Александр Медведский, известный проповедник.
В послевоенные годы, на пожертвования православных горожан, в храме регулярно проводятся комплексные реставрационные работы, благоустройство территории вокруг храма. В 1982 году в ограде собора построен новый церковный дом.
В 1987—89 гг, в ознаменование 1000-летия Крещения Руси, была произведена реставрация соборных икон, позолота пяти глав храма, ремонт его фасадов и интерьеров.
Николо-Богоявленский кафедральный собор — одна из главных православных святынь города на Неве. В храме находится частица мощей св. Николая Мирликийского вместе с частицей мощей св. Александра, мученика I века, переданной в собор императрицей Александрой Федоровной, супругой Николая I.
Очень почитается в народе храмовая икона св. Николая Чудотворца, писанная по липовой доске, чисто греческого письма, середины XVII века и подаренная греческими моряками в храм, стоявший на месте Никольского собора до его постройки.
В серебряном окладе покоится медальон с частицей мощей Святителя Николая, привезенный митрополитом Гор Ливанских Илией Карамом из Бари и подаренный в 1960 году в день празднования 200-летия храма. Пред чтимой иконой ежедневно совершаются молебны, в среду вечером и в четверг, после каждой литургии, всенародно поется акафист святителю Николаю. Кроме того, в нижнем храме находятся почитаемые иконы Божией Матери «Казанская», «Владимирская», «Троеручица», «Знамение Божией Матери».
Верхний храм во имя Богоявления Господня — более светлый и просторный. У северной стены верхней церкви стоит небольшой саркофаг-мощевик красного дерева, ранее подаренный Русским Пантелеймоновым монастырем на Афоне Афонскому подворью в Петербурге. С закрытием подворья в 1930-х годах эта святыня была перенесена в Николо-Богоявленский собор.
Перед царскими вратами верхнего храма стоит резное вызолоченное царское место, обитое внутри темно-малиновым бархатом с резной вызолоченной короной наверху и буквами Е. П. У левого столпа перед иконостасом находится резная вызолоченная кафедра.
В начале этого века, одновременно с сооружением в Никольском сквере, рядом с собором, памятника морякам броненосца «Император Александр III», погибшим в 1905 году, на южной стене верхнего храма были установлены две мраморные доски морякам, павшим в русско-японскую войну 1904—1905 гг.
Традиции прежнего Морского собора не прерываются и поныне. 27 мая 1990 года в день 85-ой годовщины Цусимского сражения, митрополитом Ленинградским и Новгородским Алексием торжественно была отслужена панихида по русским морякам, погибшим в том сражении.
В 1989 году, с благословения митрополита Ленинградского и Новгородского Алексия (Ридигера), ныне Святейшего Патриарха Московского и Всея Руси Алексия Второго, в храме была установлена доска в память 42-х моряков-подводников, погибших у берегов Норвегии, с надписью: «Подводникам Русского флота. Взяты морем 7 апреля 1989 года. Вечная память».
На северной стене верхнего храма висит киот с образом св. Апостола Петра, сооруженный на стоимость серебряных венков, возложенных в 1893 году на гроб П. И. Чайковского от Русской оперы, Мариинского театра, музыкальных училищ и частных лиц.
На южной стене находится икона св. прор. Анны, по преданию пожертвованная в храм А. А. Ахматовой.
Храмовыми праздниками в Николо-Богоявленском кафедральном соборе являются дни:
6 (19 н. ст.) января — Богоявление Господне; 9 (22) мая — день перенесения мощей св. Николая Чудотворца из Мир Ликийских в Бар-град (Бари); 24 июля (6 авг. н. ст.) — день Рождества Иоанна Предтечи, день Чесменской победы над турецким флотом; 29 августа (10 сент. н. ст.) — день Усекновения Главы Иоанна Предтечи; 21 сентября (3 октября) — день обретения мощей св. Димитрия Ростовского; 6 (19) декабря — день св. Чудотворца Николая Мирликийского.