«Волостка Коложма, а в ней церковь Климент» упоминается в рукописи «Летописец Соловецкий…», а также в датированной 1683 годом благословенной грамоте об освящении вновь устроенного храма во имя священномученика Климента. В «Кратком историческом описании приходов и церквей Архангельской епархии«, сообщается, что в 1871 году в Колежемском приходе на средства прихожан была построена деревянная однопрестольная церковь в честь святого священномученика Климента, а в одной версте от церкви находилась деревянная Покровская часовня.

«Архангельские епархиальные известия» 15 августа 1910 года (№16, часть неоф. стр. 550) сообщают о том, что Иван Васильевич Кочин (21.02.1836–22.06.1910), за свою жизнь составивший «значительное состояние рыбными промыслами на Мурмане и торговлей рыбой в Петербурге», в 1870 году отремонтировал в Колежме Климентовскую каменную церковь, а став в 1898 году председателем попечительства Колежемского прихода, он «успел построить 3-х престольный, деревянный храм, благолепный по виду, собрав на это попечительских сумм около 2000 руб., пожертвований от разных лиц 1410 руб. и из личных средств, израсходовав больше 6000 руб.». С 1897 по 1900 годы Иван Васильевич Кочин содержал школу грамоты для девочек, кроме того, оплачивал квартиру для министерского училища с. Колежмы. Он был награжден тремя нагрудными медалями: серебряной и двумя золотыми. 22 июня (по ст. ст.) 1910 года его не стало: он простудился, слег и уже не вставал. Его похоронили на приходском кладбище, в полутора верстах от церкви рядом с сыном Василием…

«Архангельские епархиальные ведомости» 1901 года сообщают о колежемском священнике Матвее Ильинском, который более 20 лет служил в Колежемском приходе, был тружеником, «обратившим приход в лучший», несмотря на то, что это было связано с определенными трудностями. Благодаря отцу Матвею в селении Колежме появилась школа: сначала в «убогой хате», затем – в наемном помещении, а позже – в особом здании, где вместе с правлением он основал сельское училище, обучая и мальчиков, и девочек. И не один год, а двадцать лет. Когда училище не стало вмещать всех желающих учиться, на его предложение открыть школу для девочек откликнулось 20 новых учениц. К сожалению, о работе данной школы подробно не сказано.

Занимаясь с местными ребятишками, отец Матвей не забывал и о приходском храме. Именно при нем церковь была обеспечена двумя большими пожнями, дававшими храму ежегодно до 100 рублей. Был куплен и дом для священника, выстроена трехпрестольная деревянная церковь. К несчастью, через месяц после освящения она сгорела. Тогда отец Матвей привел с прихожанами «в лучший вид» старую каменную церковь. После отъезда его из Колежемского прихода сюда приехал служить отец Иоанн Щеколдин, продолживший дело М. Ильинского. Но кроме школы, он избрал еще и путь «домашних собеседований» с местными жителями.

1 февраля (по ст. ст.) 1903 года в селе произошло важное событие: был освящен главный престол во имя Сретения Господня строящейся трехпрестольной церкви. Просторный храм, переполненный молящимися, освящали о.о. благочинный Н. Канорский, Сумского прихода Анатолий Теремицкий, Колежемского прихода И. Васильев и Виремского прихода В. Видякин в «сослужении дьякона Сумского прихода Ф. Пашина и при участии двух псаломщиков и местного любительского хора».

Источник 1910 года сообщает: «Село Колежма существует издавна, и было, как большинство приморских селений, вотчиной Соловецкого монастыря. Монастырем, вероятно, были устроены в Колежме и 2 храма: деревянный, во имя Сретения Господня, и каменный во имя Климента. Деревянная церковь 2 раза подвергалась пожару, каменная стоит до сего времени» (См.: Из с. Колежмы Кемского уезда // АЕВ. – 1910. – 15 авг. (№16). – Ч. неоф. – С. 551.).

Далее сообщается, что когда в 1870 году вторично сгорела Сретенская церковь, «стараниями Ивана Васильевича Кочина была отремонтирована и приведена в более или менее приличный вид (через пристройку деревянного алтаря и трапезы) Климентовская каменная церковь, каково здание до сего времени у волостных заправил раскольников служило хлебным амбаром».

О Сретенском храме села Колежма, который был построен в 1903 году, известно, что в 1937 году  он был преобразован в молодежный клуб.

Архивные источники 1834 года сообщают о том, что Колежемский приход состоял из двух церквей — деревянной холодной Сретения Господня, стоявшей на каменном фундаменте, и каменной теплой Климентовской, построенной в 1820 году. Рядом с ней находилась деревянная колокольня на каменном фундаменте.

В описании 1869 года указывается, что Сретенская церковь была построена в 1869 году на добровольные пожертвования прихожан и посторонних из разных мест России, освящена 1 февраля 1869 года.

Архивные источники 1882 года указывают на наличие в Колежемском селении одной каменной церкви и одной деревянной часовни, а более ранние, 1870 года, сообщают о «сгорении» новой деревянной церкви со всем имуществом в ночь с 20 на 21 ноября 1870 года. Эта церковь, указано в документе, была построена в 1869 году.