Первая Божественная Литургия с Архиерейским служением в истории поселка Оленья Губа, где никогда не было православного храма, состоялась 24 ноября 2015 года в одной из квартир, приспособленной под домовую церковь. С этого момента началась подготовка к строительству полноценного храма во имя св. блгв. князя Александра Невского. Местная религиозная организация приход храма благоверного великого князя Александра Невского поселка Оленья Губа зарегистрирована 16 мая 2016 года.
19 октября 2017 года в посёлке Оленья Губа состоялась закладка камня в основание фундамента под строительство храма в честь св. блгв. князя Александра Невского. Закладкой и освящением камня в основание нового храма ознаменовалось завершение первого этапа строительства в Оленей Губе. Чин освящения совершил епископ Североморский и Умбский Митрофан.
20 июня 2020 года в строящемся храме состоялась первая Божественная Литургия. Богослужение возглавил епископ Североморский и Умбский Тарасий (Баданин) в сослужении благочинного Александровского благочиния протоиерея Сергия Мищенко, настоятеля прихода протоиерея Леонида Сулоева, протоиерея Дионисия Иванова, протоиерея Сергия Шерфетдинова, иеромонаха Никодима (Коливатова) и иеродиакона Феодорита (Линкова). В настоящее время продолжается строительство храма.