Приход открыт в 2000г. Здание храма сооружено на средства прихожан: И.И. Кулакова, А.Л. Сорокина, А.П. Болдарь, Г.П. Бельского и др. и жертвователей: ОАО «Знамя», ООО «Шушан», шахты №12, шахты «Краснокаменская», Киселевское ПТУ. 11 июня 2000 г. по благословению архиепископа Софрония протоиереем Михаилом Яськовым было освящено место под строительство основного храма и закладной камень. Александро-Невский храм находится в восточной части города Киселёвска, в жилом районе, расположенном вблизи крупного промышленного предприятия по производству взрывчатых веществ ОАО «Знамя». Здание храма органично вписывается в окружающий ландшафт. Золотисто-желтая окраска его фасадов великолепно сочетается с зеленью высоких сосен, окружающих здание церкви – эта цветовая гамма радует глаз круглый год.
С 2001 г. службы проводились в подвальном помещении храма. Завершенное в 2006 году строительство храма явилось духовным и архитектурным подарком к 70-летнему юбилею города. Первоначальный проект храма был разработан Новокузнецкой творческой мастерской архитектора Виктора Николаевича Усольцева. В процессе строительства, проектируемое в стиле классицизма здание изменялось и дорабатывалось, приобретая оттенки эклектики. Дополнения вносились, исходя из условий целесообразности использования его помещений. Храм увенчан тремя главами, обшитыми пластинами с титановым покрытием. Установлены купола на восьмериках с восемью колоннами. Звонница, расположенная над западным входом, имеет форму восьмеричной аркады. Карнизы здания украшены барельефным геометрическим орнаментом. На северной и южной стенах, между оконными проемами, имеются барельефные изображения православного креста. Центральное и боковое крыльцо выполнено из цветного бетона с добавлением мраморной крошки. Металлические решетки ограждения, перила, козырьки главного и боковых входов, фонарные столбы – все украшено изящной и легкой ажурной ковкой. Интерьер храма отличают живописные композиции, основанные на сюжетах Ветхого и Нового Завета, жития св. блгв. Кн. Александра Невского и других святых на стенах, своде, парусах. Алтарная часть завершается резным иконостасом. Освещает храм изысканное паникадило со множеством свечей.
Храм освящен 12 сентября 2006 года епископом Кемеровским и Новокузнецким Аристархом (ныне митрополитом кемеровским и Прокопьевским).
