В 1997 году, 7 мая, на самом краю Мурманской области, в городе-гарнизоне подводников Гаджиево родилась церковная община. Администрация города выделила помещение в жилом доме, освященное 10 октября 1997 года Владыкой Симоном, тогда Епископом Мурманским и Мончегорским, в честь Святого апостола Андрея Первозванного. Поначалу приход окормлялся благочинным, а 13 марта 1998 года был назначен настоятелем игумен Аввакум. Стали регулярно совершаться богослужения.
10 октября 2004 года по благословению Владыки Симона освятили место для строительства нового храма на пустыре, рядом с действующим. Проект храма был утвержден в 2017г. Через год с небольшим в воскресенье, 16 сентября 2018г. епископ Североморский и Умбский Митрофан и митрополит Ташкентский и Узбекистанский Викентий в сослужении духовенства Североморской епархии и Екатеринбургской Митрополии совершили чин Великого освящения храма. Реализация такого масштабного проекта в столь короткие сроки стала возможна благодаря попечению екатеринбургских меценатов, организовавших в 2001 году фонд «Помощи экипажам ракетных подводных крейсеров стратегического назначения «Екатеринбург» и «Верхотурье».