Начало строительства храма было положено в феврале 2003 года. Распоряжением Департамента градостроительства Администрации города Красноярска был выделен земельный участок под строительство храма. В этом же году был создан попечительский совет и фонд содействия строительству храма Рождества Христова г. Красноярска. Автором проекта храмового комплекса стал архитектор В.И. Ульянов. Проектно-сметная документация была разработана двумя институтами: Красноярскгражданпроект и Красноярсгорпроект.

В марте 2006 года архиепископом Красноярским и Енисейским Антонием был освящен закладный камень на месте строительства храма. Закладка нового просторного храма в Кировском районе Красноярска состоялась в 2006 году. Чин Великого освящения храма совершил сам Патриарх Кирилл 12 сентября 2012 года. Высота Рождественской церкви – 47 метров, вместимость – свыше 1000 человек, на данный момент это самый крупный храм города. В вечернее время обеспечена красивая подсветка.