Во время осады Севастополя в годы Крымской войны 1854-1855гг. тела убитых и умерших от ран перевозили на Северную сторону и хоронили сначала на Михайловском кладбище, а затем на различных высотах. Со временем на большом пустынном высоком холме сформировалось братское кладбище. Здесь покоятся также ветераны Крымской войны, умершие значительно позже, вдали от Севастополя. Так похоронены были генералы С.А. Хрулёв, Э.И. Тотлебен, М.Д. Горчаков, а также многие другие адмиралы и офицеры.
После Крымской войны А.А. Авдеев проектирует и строит свои известные творения: часовню на Инкерманских высотах близ Севастополя (1886 г.) в память смотра русской армии, произведенном в 1855 году Александром II (окончена в 1886 году, но, к сожалению, не сохранилась), часовню на могиле князя М.Д. Горчакова, храм во имя Святого Покрова в Ореанде, памятник на могиле капитана 1-го ранга А.И. Казарского в Николаеве. Он же является автором проекта Владимирского собора, сооруженного на вершине Центрального холма в Севастополе.
5 сентября 1857 года были освящены и заложены первые камни храма во имя Святителя Николая Чудотворца. Под закладные блоки положили медали: «За защиту Севастополя» и «В память войны 1853—1856 гг.». В августе 1861 года в Севастополь прибыл Александр II с императрицей Марией Александровной и младшими детьми — Павлом, Сергеем, Алексеем и Марией он посетил Братское кладбище и Херсонесский монастырь, где заложил первый камень и установил деревянный крест в основание будущего храма в честь Святого Равноапостольного князя Владимира. Храм на Братском кладбище благословили назвать именем одного из самых почитаемых в Православии святых — Николая Чудотворца (Мирликийского). А.А. Авдеев и члены комиссии, контролировавшие строительство всего комплекса Братского кладбища, рассчитывали возвести храм за три года. Никто не предполагал, что оно растянется на долгие тринадцать лет. Работа продвигалась крайне медленно и, в основном, из-за нехватки средств. Пожертвования поступали из многих городов и разных уголков России. Присылали деньги офицеры и чиновники, родственники погибших воинов в Севастополе, солдаты и матросы. Но денег катастрофически не хватало. Комиссия принимает решение о временном приостановлении строительства. Прекратили выплачивать жалованье А.А. Авдееву. Архитектор уехал в Петербург, а, возвратившись, занимался некоторое время только возведением Владимирского собора. Критическое финансовое положение несколько спасла княгиня Татьяна Васильевна Васильчикова, пожертвовав в 1863 году двенадцать тысяч рублей и пообещав, что в последующие три года будет давать на строительство по столько же. Но уже в том же году комиссия приходит к выводу, что недостроенный храм требует ремонта. Из-за сырости местами отвалилась штукатурка, здание дало осадку, на стене появилась трещина, стали проседать гранитные ступени крыльца.
Осенью 1860 года, когда был установлен крест весом в 1500 пудов, вырубленный из диорита, добытого в районе Аю-Дага, поперечная часть его обломилась. К счастью, жертв не было, не сильно пострадало и здание: повреждение получили только фронтоны. Новый крест водрузили в феврале 1864 года, завершив, в целом, строительство храма в виде усеченной пирамиды. Она квадратная в плане (20,5 м), сложена из местного крымбальского известняка.
Высота пирамиды 27 метров. Ее основанием служит высокий цоколь, сложенный из квадров, обработанных крупным рустом. Квадры прочеканены свинцом, отлитым из пуль, собранных на местах сражений. С четырех сторон пирамиды находятся ризалиты. В них с севера на юг устроены окна вытянутых пропорций, в восточном ризалите, где помещается алтарь, окна отсутствуют. В толщину стен пирамиды врезаны узкие окна с сандриками, выше — арочные проемы с колоннами дорического ордена, ведущие в небольшую звонницу. На гранях пирамиды вмонтированы плиты из темного гранита с перечислением воинских соединений, принимавших участие в обороне, временем пребывания в осажденном Севастополе и понесенных потерь. Напоминая о важном событии в военной истории Отечества, они удачно вписались в памятник, подчеркивая строгую индивидуальность храма-пирамиды. 24 мемориальные доски с наименованиями частей войск севастопольского гарнизона установлены к 50-летию первой обороны и на церкви Святого архистратига Михаила.
В 1870 году все строительные и отделочные работы были завершены и в присутствии генерал-адмирала Великого князя Константина Николаевича — младшего брата Александра II, храм Святого Николая освятили.
В 1910-х годах отремонтировали ограду кладбища и некоторые памятники. Из Никитского ботанического сада привезли и высадили около 300 деревьев и 200 кустарников, в том числе роз. У дома священника соорудили ограду, устроили водоснабжение.
В 1911 году симферопольский художник Николай Степанович Лапин промыл в храме мозаику. Но на этом работы на Братском кладбище завершились — и надолго. Грянул 1917-й год….
После революционных событий отношения атеистического Советского государства и церкви оказались сложными и подчас трагичными. Ликвидировались религиозные общины, закрывались храмы и монастыри, разрушались, стирались с лица земли ценнейшие исторические и архитектурные памятники русского культового зодчества. Храму Святого Николая повезло, его не снесли, как в Балаклавском Георгиевском монастыре — древнейший храм Святого Георгия Победоносца, в котором в сентябре 1820 года, при посещении обители, бывал Александр Пушкин, как храм Святого Николая в Инкермане, часовню Святого Георгия Победоносца в Кады-Кое...
29 октября 1941 года в Севастополе объявили осадное положение: на подступах к нему появился враг. Началась оборона города, продолжавшаяся долгих 250 дней и ночей. Братское кладбище оказалось в четвертом секторе Севастопольского оборонительного района.
С декабря 1941 года на кладбище расположился командный пункт четвертого сектора, а звонницу храма артиллеристы облюбовали для корректировки огня. В 1942 году на территории некрополя находился «взвод разведки штабной батареи». Известны и некоторые из них: Довлет-Кужин, Лукьянов, Михайличенко, Ратушников, Шибанько, Шиманский...
Спустя двадцать восемь лет — 11 ноября 1970 года при расчистке храма обнаружат их журнал наблюдения. Вот несколько торопливо написанных карандашных записей, относящихся к маю-июню 1942 года: (24 мая).
«10 ч. 15 мин. — противник вел минометный огонь в районе Золотого гребня (так называли небольшую возвышенность и вал у Любимовского аэродрома местные жители и защитники Севастополя 1941—1942 гг. из-за их ярко-желтого цвета). Бросил 27 мин.
20 ч. 30 мин. — противник вел минометный огонь в районе домика по переднему краю обороны, бросил 16 мин.
20 ч. 40 мин. — противник вел минометный огонь в районе домика, бросил 13 мин.
22 ч. 30 мин. — минометный огонь в районе Золотого гребня. Бросил 6 мин. По фронту редко ружейно-пулеметная перестрелка и освещение ракетами…».
Последние строки журнала, даты нет. «Всего за смену с 4 до 8 ч. утра налетов — 296, артиллерийский огонь — около 600 снарядов. С 11 до 12 ч. налет самолетов противника — 308 штук». Во второй половине дня 17 июня противник, прорвав укрепления на участке 95 стрелковой дивизии, овладел территорией Братского кладбища, где находился штаб дивизии. На Северной стороне — на Константиновском и Михайловском фортах, в районе Инженерной пристани и в Сухарной балке были созданы опорные пункты, командиры которых получили приказ удерживать их до последнего патрона. Защитники этих опорных пунктов приняли неравный бой: истекая кровью, Севастополь сражался — час за часом, минута за минутой. 30 июня 1942 года все возможности организованной обороны города были исчерпаны. Но на мысе Херсонес и у 35-й береговой батареи севастопольцы еще держались несколько суток — до двенадцатого июля. Наступили долгие месяцы оккупации. Но ровно за год до великой победы над фашизмом, 9 мая 1944 года советские войска освободили город русской славы.
В июне 1942 года во время артобстрела и авиационного налета обрушилась верхняя часть пирамиды, крест при падении раскололся на три части. Получили повреждения мемориальные доски внутри и снаружи храма, иконостас. Из 644 кв. м. общей площади мозаичной живописи было утрачено более половины — 357 кв. м. Предстояла огромная кропотливая работа по реставрации храма-памятника и всего мемориального комплекса Братского кладбища. Приближался 100-летний юбилей первой обороны города.
Проект реставрации храма разработал в Киеве научно-исследовательский реставрационный отдел Украинского специализированного научно-производственного управления под руководством И.Л. Шмульсона.
20 февраля 1967 года Совет Министров УССР принял постановление «О состоянии и мерах по дальнейшему улучшению охраны и сохранения памятников архитектуры, археологии и истории Украинской ССР». Не забыли в нем и о Братском кладбище. В июне 1968 года специалисты Крымского реставрационного участка №5 приступили к восстановительным работам. В бригаде строителей, которой руководил Василий Степанович Смолянинов, работали мастера: Г.М. Сухарев, В.И. Шама, Б.Г. Панфилов, Н.Г. Шарый, А.И. Белов, М.А. Пчелинский, Е.Н. Жеребцов. Привлекались и другие специалисты.
При расчистке верхней части храма строители обнаружили останки немецкого пулеметчика, выбравшего удобную позицию, видимо, в мае 1944 года. Нашли и его пулемет с не дострелянной лентой. Там же, в северо-восточной стороне храма, наткнулись на неразорвавшийся снаряд, застрявший в стене. Приехавшие саперы осторожно извлекли и обезвредили опасный сюрприз, оставшийся от войны, а строители продолжили работу.
В 1971 году храм Святого Николая был восстановлен, за исключением креста. Расколовшийся на три части диоритовый крест в Севастополе реставрировать не удалось. Его отвезли в Киев, где после долгих споров и раздумий, нашли правильное решение, позволившее в 1974 году водрузить уникальный крест на вершине храма-пирамиды. Впереди же предстояла огромная ответственная работа по консервации и реставрации интерьера храма.
