В 1860 году Святейший Синод решил построить несколько православных храмов внутри Лапландии "как в карельских приходах" и выделил для этого необходимые средства. В 1862 году Духовное правление открыло приход в Нотозерском погосте и направило для устройства церкви и причтового дома со службами священника Георгия Кирилловича Терентиева, известного своей "расторопностью, опытностью и усердием", какой необходим для "святого дела... в отдаленном и пустынном крае".
Для строительства храма отец Георгий избрал урочище на реке Ноте, в 7 верстах выше Падуна, в 5 верстах от зимнего лопарского погоста Нотозеро. Первые три года ушли на заготовку строительных материалов: для церкви потребовалось 2 132 бревна, а также кирпич, гвозди, стекло и многое другое. К сооружению церкви артель из 12 плотников приступила в марте 1865 года и закончила строительство в 1869 году. Храм обошелся в 1 782 рубля 41 копейку, причтовый дом с подсобными зданиями — в 970 рублей.
11 ноября 1864 года Георгий Терентиев обратился в Консисторию с просьбой выслать храмозданную грамоту "на основание церкви во имя Великомученика Георгия Победоносца". Однако епархиальное начальство приняло решение строить храмы в Нотозере и в Ловозере во имя Богоявления Господня, "потому что лопари всех погостов съезжаются в день Богоявления Господня, в который происходит у них род сельской ярмарки".
Богоявленская церковь в Нотозере была сооружена по проекту, присланному из Святейшего Синода, и представляла собой небольшой, но довольно красивый храм. К зданию церкви уравновешенно примыкали с одной стороны алтарь, с другой — паперть с крыльцом, над которой возвышалась шатровая звонница с чешуйчатой главой и крестом. Клетская церковь несла восмиугольный, крытый тёсом и окрашенный медянкой шатер с шейкой, главкой и крестом общей высотою 21,3 м; с южной и северной сторон имелось по три окна.
В 1898 году наружные стены церкви были обиты тёсом и выкрашены, обновленную крышу покрасили "смолой с суриком".
Церковь была освящена в январе 1873 года. В это время в. Нотозерском приходе состояло 60 дворов и 312 человек, из них в Сонгельском погосте 22 двора и 127 крестьян-лопарей.
Прихожане дали причту весьма уловистую сёмужью тоню Верхний Пудас, сенокосы в окрестностях церкви, а в 1913 году казна отмежевала церкви 33 десятины "под расчистку для сенокосов".
В зимнее время лопари охотно посещали церковь, богослужения шли часто. Летом они расходились в разные места для промысла, приезжали к церкви лишь в большие праздники, давали пожертвования.
В 1914 году в приходе состояло 70 лопарских дворов и 501 человек, в том числе в самом Нотозере 36 дворов и 298 жителей. Священником служил Виталий Михайлович Черняев. Церковь имела скромный, но благолепный иконостас, "утварью, ризницею и богослужебными книгами снабжена достаточно".
http://www.dobrohot.org/progress/hks.html#__RefHeading__2278_1219275644
Место Богоявленского храма было затоплено в связи с созданием Верхнетуломского водохранилища.