В годы Великой Отечественной войны в Сталинске (Новокузнецке) создаётся православная община. Во главе этой общины были два пожилых человека. Одного все назвали старцем Адрианом, другой был известен как Тимофей Никитович Литуев. В 1947 году община приняла решение о приобретении небольшого дома для своих молитвенных собраний. Был приобретен дом № 25 в Пионерском переулке. Деньги за дом были уплачены из личных сбережений старцев. Зарегистрировали молитвенный дом в 1947 году накануне дня чествования Архангела Михаила. Первым настоятелем храма стал протоиерей Николай Шетнев. Прихожан становилось с каждым годом больше. Молитвенный дом приходилось постоянно расширять методом пристроек. Позднее назрела необходимость в постройке нового здания. В 1975 году новым настоятелем храма стал Александр Пивоваров.

В июне месяце того же года добровольные труженики из прихожан во главе с настоятелем самовольно приступили к работам в церкви. Строился храм вопреки атеистическим веяниям того времени. Строили здание преимущественно пожилые люди. В 1976 году основное строительство было завершено. 21 ноября 1976 года храм был освящен епископом Гедеоном. Тогда же была совершена и первая архиерейская Литургия с крестным ходом вокруг.

Написанием икон для храма с 1976 года и более трёх лет занимался художник-самоучка из Томского Петро-Павловского собора Серапион Фёдорович Вепрев. Работы выполнены на кедровых щитах по левкасу с последующим покрытием сусальным золотом и чеканкой. Над убранством храма работали также художники из Москвы, Новокузнецка, Томска. Местный столяр-краснодеревщик и резчик Борис Маркович Джерихов изготовил Распятие-Голгофу с предстоящими Божьей Матерью и апостолом Иоанном Богословом, резную гробницу для хранения святой Плащаницы, а также кресло с постаментом на Горнее место. Из Белоруссии были доставлены две старинных металлических хоругви, которые стоят у подклиросных киотов. Нижний этаж храма был благоустроен под придел трёх Святителей: Василия Великого, Григория Богослова и Иоанна Златоуста. Иконы выполнены разными мастерами: из Москвы, Минска и двумя студентами из Академии художеств из города Владивостока.

После завершения строительства нижнего предела, началось строительство Крестильного храма в честь Иоанна Крестителя. Длина и ширина здания – 24 на 12 метров, а высота потолков 5 метров. Там устроен полноценный алтарь. Художники из Москвы, под руководством Евгения Владимировича Тихомирова, изготовили все иконы для иконостаса в Крестильный храм, а также настенные картины по Виктору Михайловичу Васнецову на тему Крещения Руси. Освятили храм в 1979 году. В 1980 году выполнена работа над главным иконостасом и подклиросными киотами. К дням Страстной седмицы в 1986 году была получена из Пюхтицкого монастыря старинная Плащаница Христа Спасителя, которая была капитально отреставрирована. В 1995-1996 годы бригадой специалистов из города Томска все оконные рамы в здании храма и алтаря были заменены цветными витражами.

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