История Свято-Николаевского собора тесно переплетается со своей предшественницей на берестейской земле - Свято-Николаевской церковью, разобранной в угоду создания Брестской крепости. О том храме остались лишь рисунки на гравюрах и документы Брестской Унии 1596 года. Собор во имя святителя Николая Чудотворца был создан как гарнизонный храм на территории строящейся крепости города. Он был заложен в 1851 году, когда в городе не было ни одного действующего православного храма, и военские чины должны были довольствоваться временным церковным помещением в здании бывшего римо-католического базилианского монастыря. Средства на него собрали офицеры гарнизона и духовенство. Храм вчерне окончили уже к концу 1850-х годов, но пятиглавая церковь из-за своей высоты оказалась не соответствующей стратегическим целям крепости, а потому в середине шестидесятых годов ее разобрали, и в 1872 году вторично перестроили. Однако, и эту церковь пришлось были разобрать, так как она, вследствие несоразмерной тяжести сводов, дала трещины во многих местах.

Наконец в июле месяце 1874 года был начат, а в 1876 году благополучно окончен третий крепостной собор. План собора был составлен академиком Российской академии художеств архитектором-профессором Д. И. Гриммом, а строителем его был военный инженер капитан Л. М. Иванов. Храм был сооружен на отпущенные военно-инженерным ведомством суммы, в количестве 139,976 руб. 59½ коп., из которых 48,000 руб. уплачено Петербургскому Обществу взаимного вспомоществования русских художников за внутреннюю отделку и живописные работы. Величественный храм-базилика имел только один престол. Купол храма венчал Георгиевский крест. Считается, что отапливался храм с помощью каминов как дворцы или бани. Собор был обнесен каменной стеной, среди роскошного сквера. 21 августа 1877 года он был торжественно освящен, в присутствии всего крепостного гарнизона, епископом Брестским Ианнуарием.

 

В предреволюционный период собор был вполне обеспечен ризницей и утварью, при нём действовали две школы, была приписана церковь Александра Невского при крепостном госпитале. По штату при соборе были положены настоятель - протоиерей, два священника, диакон и псаломщик. Среди икон собора примечательной был образ святителя Митрофана Воронежского, доставленный 3 июня 1840 года инженер-майором М. Г. Евреиновым, по повелению императора Николая I, в память перевезения водою из Бобруйска в Брест-Литовск первых артиллерийских снарядов. <_o3a_p>Со времени освящения до 12 июня 1890 года собор состоял в ведомстве Литовской епархии, но затем, по Высочайшему повелению, был перечислен в ведомство протопресвитера военного и морского духовенства. В 1906 году храм был расписан в романском стиле, наименован "Николаевским гарнизонным собором" и стал главным воинским храмом Западного приграничного округа. Храм посещали все императоры от Александра I до страстотерпца Николая II. <_o3a_p>

Первая мировая война обрушила на собор и первые снаряды. В 1915 году вглубь России были эвакуированы колокола. После занятия Бреста Польшей в 1919 году, и официального включения этого края в состав Польши по Рижскому мирному договору 18 марта 1921 года, храм оказался в руках у римо-католиков. В 1922-1930 годах его перестроили до неузнаваемости и превратили в римо-католический гарнизонный костёл святого Казимира по проекту польского архитектора Ю. Лисецкого. Фасад храма стал напоминать вид костёла августинцев, некогда существовавшего на территории старого Бреста. 

С приходом красной армии в 1939 году и включением Бреста в СССР собор был переоборудован под гарнизонный клуб. Накануне вторжения немецких войск он использовался как клуб 84-го стрелкового полка. В ходе боёв в июне 1941 года здание стало важным пунктом обороны, так как расположено на самом высоком месте острова, откуда хорошо просматривается вся территория крепости. Здание не раз переходило из рук в руки и стало одним из последних очагов сопротивления советский воинов в цитадели. Весь храм был изуродован пулями, осколками гранат, снарядов и бомб, но всё-таки устоял.На его стенах осталась надпись защитников, пишущих, что умрут, но из церкви не уйдут.

В 1960-е годы была произведена консервация здания в ходе строительства мемориала "Брестская крепость-герой" и в таком виде оно простояло до 1990-х годов. 

В 1994 году собор был возвращен Православной Церкви в удручающем состоянии, начались работы по его реставрации. Процесс восстановления был сложен и требовал больших затрат, реконструкция велась за счет пожертвований прихожан, при содействии областных и городских властей, силовых структур. 

С осени 1995 года в Никольском гарнизонном соборе стали совершаться Богослужения, в зимний период - в нижнем храме. Первая Божественная литургия была совершена в 1996 году. 22 мая 1999 года над востановленным куполом храма был воздвигнут и освящен новый крест. 18 июня 2001 года на звоннице был поднят бронзовый колокол весом 1 тонну: один из крупнейших колоколов отлитых за последние 100 лет в Белоруссии. 

   

24 июня 2001 года патриарх Московский и всея Руси Алексий II, еще в 1995 году отслуживший в соборе заупокойную службу, освятил верхний престол храма. В декабре 2003 года в дар для звонницы были переданы 7 колоколов от правительства Украины с надписью на больших колоколах: "В память защитников Отечества. Леонид Кучма". В 2004 году храм украсило семиярусное паникадило с двенадцатью иконами и сто четырьмя свечами. Восстановительные работы, нацеленные на воспроизведение исторического убранства собора, продолжались и впоследствии.