Строительство храма Рождества Христова при Новокузнецкой духовной семинарии (ныне Кузбасской семинарии) в Орджоникидзевском районе г. Новокузнецка началось летом 2000 года в память о 67 горняках, погибших 2 декабря 1997 года при взрыве газа метана на шахте «Зыряновская».

Текст памятной доски на северной стене храма гласит:

«Храм Рождества Христова в городе Новокузнецке милостию Божией, по инициативе губернатора Кемеровской области А. Тулеева и по благословению Высокопреосвященнейшего архиепископа Софрония, первого управляющего Кемеровской и Новокузнецкой епархией, возведен в память обо всех погибших шахтерах Кузбасса. Строительство было начато в 2000 году в Орджоникидзевском районе в связи с тем, что здесь 2 декабря 1997 года на шахте "Зыряновская" погибли 67 горняков. Финансовые трудности не давали возможности быстро завершить работы. Но люди молились и верили, что Господь не оставит это святое дело. В 2008 году по совместному решению губернатора А. Тулеева и управляющего Кемеровской епархией епископа Аристарха строительство возобновилось. Деньги на храм собирали поистине всем миром. Огромное желание, финансовая поддержка угольных компаний, подвижнический человеческий труд позволили завершить строительство. 23.08.2012, в канун Дня шахтера, митрополит Кемеровский и Прокопьевский Аристарх совместно с духовенством области совершил благодарственный молебен по окончании строительства, и в храме начались богослужения. Да поддержит Господь силы родственников погибших шахтеров, дарует радость Воскресения и ниспошлет благополучие земле Кузнецкой и всем ее жителям!»

После трагедии 1997 года премьер-министр России В. Черномырдин пообещал помочь семьям погибших и на государственные средства построить православный храм. Обещанные средства были выделены в конце 2000 года областному ГлавУКСу (Главному управлению капитального строительства) г. Кемерово на проектирование и строительство храма-мемориала погибшим шахтерам. Решение о строительстве мемориального комплекса было принято по согласованию правящего архиерея архиепископа Кемеровского и Новокузнецкого Софрония с областными и городскими властями, чтобы в перспективе совместить в единый духовный центр мемориальный комплекс с собором и Новокузнецкое духовное училище. Между ПИ «Кузбассгражданпроект» и ГлавУКСом был заключен договор на проектные работы. Архиепископ Софроний благословил архитектора В.Н. Усольцева для проектирования эскиза собора.

В конце января — начале февраля 2001 года строительной компании «Южкузбасстрой» были выданы чертежи свайного поля. Спустя 11 месяцев работы прекратились из-за отсутствия средств. На тот момент был выполнен только нулевой цикл.

Семь лет ушли на устные и письменные обращения к администрации города и области. Собирались подписи вдов и матерей погибших шахтеров и других жителей города о необходимости возобновления строительных работ.

В 2008 году по инициативе губернатора Кемеровской области А.Г. Тулеева в рамках соглашения между областной администрацией и Кемеровской епархией было принято решение о возобновлении строительства собора. Был создан благотворительный фонд, возобновлены и отправлены на доработку архитектурно-строительные документы. Все работы взяла на себя строительная компания «Новокузнецк» под кураторством главного Управления капитального строительства Кемеровской области.

18 августа 2008 года в Орджоникидзевском районе на стройплощадке собора Рождества Христова благочинный церквей III Новокузнецкого округа протоиерей Виктор Буглаков отслужил молебен на начало благого дела.

19 августа 2010 года, в праздник Преображения Господня, в Новокузнецке состоялось освящение восьми золоченых куполов с крестами и поднятие их на башни и колокольню строящегося собора. Главный купол, выполненный по типу центрального купола Храма Христа Спасителя в Москве, из-за большого размера и веса собирался по частям уже непосредственно на своем месте — на центральном световом барабане. По окончании работ наивысшей точкой собора и всего Орджоникидзевского района стала маковка, венчающая колокольню, которая поднимается над землей на 51,6 м. На колокольне установлены девять колоколов, изготовленных уральскими литейщиками.

В апреле 2011 года епископ Кемеровский и Новокузнецкий Аристарх совершил освящение закладного камня под строительство административно-хозяйственного комплекса при мемориале. В мае того же года началась роспись храма.

В ноябре 2011 года на восточном фасаде были установлены и освящены три первые мозаичные иконы: Святой Живоначальной Троицы, а также святых, в честь которых в дальнейшем будут освящены два из трех престолов собора: преподобного Сергия Радонежского (северный придел) и великомученицы Варвары — небесной покровительницы горняков (нижний храм).

25 августа 2013 года великое освящение храма совершил Святейший Патриарх Московский и всея Руси Кирилл.

В основу архитектурного образа собора положен тип храма «кораблем», «о девяти главах», с колокольней и пристроенными двумя, северным и южным, приделами.

Общая площадь собора составляет 3391 кв. м. Храм вмещает 2,5 тысячи человек.

Внутри храма установлен памятный канун (специальный панихидный стол) с именами всех погибших кузбасских горняков, начиная с 1920 года. Всего здесь записано 15,5 тыс. имен.

Сайт храма — http://соборрождествахристова.рф.