Храм открыт осенью 1996 года. При этом строился в период с 1993 по 1995 гг на деньги, вырученные приходом и полученные от горожан в качестве пожертвований. Проект здания был подготовлен главным архитектором города Сергеем Леушевым, который в ходе планировки стремился к сохранению традиционного карельского деревянного зодчества.
Перед входом в здание размещена скульптура Иисуса Христа, подаренная приходу местными предпринимателями. Ее автор – питерский скульптор Дмитрий Бессмертный. Необычность этой скульптуры состоит в высеченном на ней кресте затейливой формы – он повторяет крест, изображенный на иконе XII века «Спас Нерукотворный». Лик же Христа является копией Иисуса на Туринской плащанице. Из реликвий здесь также имеется икона Николая Чудотворца, написанная около 150 лет назад на деньги именитого купца Синебрюхова. Икона была привезена из Петрозаводска в день освящения храма1.
29 мая 2013 года Священным Синодом Русской православной церкви было принято решение выделить из состава Петрозаводской епархии Костомукшскую епархию и включить обе в Карельскую митрополию. В тот же день епископом Костомукшским и Кемским был избран архиерей Русской православной церкви Игнатий (в миру Алексей Михайлович Тарасов)1.
В состав Костомукшской епархии входят: