Проект храма потом доработал архитектор А.А. Авдеев: пирамида стала выше, так как в её верхней части он разместил звонницу, крест стал более массивным, в стенах появились узкие окна с сандриками. Пятого сентября 1857 года освятили и заложили первые камни храма во имя Святого Николая Чудотворца, положив под закладные блоки медали: «За защиту Севастополя» и «В память войны 1853-1856 гг.».
Возведение храма растянулось на долгих тринадцать лет, освятили его только в 1870 году. Высота пирамиды 27 метров. Её основанием служит высокий цоколь 20,5x20,5 метра, сложенный из квадров крымбальского известняка, прочеканенных свинцом, отлитым из пуль, собранных на местах сражений. Законченность пирамиде придаёт массивный четырёхконечный диоритовый крест высотой 6,8 метра на вершине. На наружных гранях пирамиды вмонтированы плиты из тёмного гранита с перечислением воинских соединений, принимавших участие в обороне, временем пребывания в осаждённом Севастополе и понесённых потерь.
Внутри пирамиды устроен крестовокупольный храм византийского стиля. В нижней части храма вмонтированы 38 серых мраморных досок. На них нанесены имена 943 погибших и умерших от ран генералов, адмиралов, штаб- и обер-офицеров. Они представляют как бы открытую поминальную книгу, по которой каждый может молитвенно помянуть имена тех, кто отдал свою жизнь, отстаивая Севастополь.
В годы второй мировой войны храм сильно пострадал, была разрушена его верхняя часть, крест при падении раскололся. Получили повреждения мемориальные доски, мозаичная живопись. Восстановительные работы завершились в 1971 году, а реставрация храма-памятника продолжается по сей день. 19 декабря 1988 года, в день Святого Николая Чудотворца, храм был освящён, и после шестидесятилетнего перерыва в нём провели службу.
В 1994 году храм передали православной общине. Над центральным порталом вновь засиял лик Христа Спасителя, выполненный в реставрационном центре Загреба. В храм пришли мощи Св. Климента, Преподобного Сергия Радонежского, Николая Угодника, Георгия Победоносца, Андрея Первозванного, святых - преподобных отцов Киево-Печерской лавры...
Свято-Никольский храм стал неотъемлемой частью исторически сложившегося ландшафта приморского города. Как столицу России невозможно представить без Кремля, Петербург без Исаакиевского собора, Киев - без Киево-Печерской лавры, так и Севастополь немыслим без доминирующего в архитектурно-пространственной композиции Северной стороны храма Св. Николая.
