2 декабря 1997 года на шахте «Зыряновская» погибли 67 горняков. Вскоре после трагедии тогдашний Председатель Правительства РФ В. Черномырдин дал обещание построить православный храм в Новокузнецке. Закладной камень был освящен и установлен 4 июля 1998 года, а летом 2000 года началось строительство Собора в честь Рождества Христова при Новокузнецкой Православной Духовной Семинарии, средства на строительство были выделены из федерального бюджета.
Однако, в конце 2001 года строительство было остановлено на нулевом цикле ввиду отсутствия финансирования.
Только в 2008 году по инициативе губернатора Кемеровской области А. Тулеева, в рамках соглашения между областной администрацией и Кемеровской и Новокузнецкой епархией, было принято решение о возобновлении строительства собора, а также был создан благотворительный фонд, возобновлены и отправлены на доработку архитектурно-строительные документы.
Дальнейшее строительство собора продолжалось на средства прихожан и пожертвования предприятий.
19 августа 2010 года были освящены восемь золочёных куполов с крестами и подняты на башни и колокольню строящегося собора. Главный купол, выполненный по типу центрального купола храма Христа Спасителя в Москве, из-за большого размера и веса собирался по частям уже непосредственно на месте — на центральном световом барабане. По окончании работ наивысшей точкой собора и всего Орджоникидзевского района Новокузнецка стала маковка, венчающая колокольню, которая поднимается над землёй на 51,6 м. На колокольне установлены девять колоколов.
К началу 2011 года по главному корпусу собора были завершены общестроительные работы, выполнены работы по устройству инженерных сетей вентиляции, отопления, водоснабжения, канализации, электроснабжения и электроосвещения. В мае 2011 года началась роспись собора.
Собор выполнен в стиле исторического эклектизма с элементами псевдорусского стиля. В основу архитектурного образа собора положен тип храма «короблем», «о девяти главах», с колокольней и двумя приделами.
Собор Рождества Христова по центральной оси «восток-запад» по проекту состоит из четырёх основных объёмов: апсиды, храмовой части, трапезной и притвора. Апсида главного престола собора в плане — квадрат со стороной 8 м, к которому примыкает полукруг с радиусом 3 м. Квадрат апсиды перекрывается лотковым сводом, цилиндрическая часть апсиды — полусферой. Естественное освещение апсиды осуществляется через четыре полуциркульных окна. С храмовой частью апсида главного престола соединена полуциркульной аркой, перед которой будет установлен иконостас главного престола.Храмовая часть главного престола представляет по проекту квадрат со стороной 16 м.
С южной стороны к храмовой части примыкает южный придел с двумя большими дверными проёмами, с северной стороны — северный придел. В западной стене храмовой части в уровне первого этажа расположены три проёма: центральный, арочный (между храмовой частью и трапезной) и два примыкающих дверных проёма, ведущие на улицу. Над арочным проёмом в уровне второго этажа располагается балкон — хоры. Освещена храмовая часть большим световым барабаном, перекрытым сводом полусферического очертания. Северный и южный приделы имеют каждый свою апсиду с иконостасом и отдельный выход с тамбуром непосредственно на улицу.
Из притворов боковых приделов по винтовым лестницам можно попасть как в цокольный, так и на второй этажи собора, а из притвора колокольни через большой дверной проём — на главное крыльцо собора с пандусом. Под центральным входом запроектирован вход в цокольную часть собора. Под храмовой частью основного престола в уровне цокольного этажа располагается крестильная комната с апсидой, купелью и двумя раздевалками.