Приход образован после обращения в православие самоедов духовной миссией под руководством архимандрита Вениамина. В приход входили самоеды, оседло жившие в с. Колве при впадении р. Колвы в Усу и кочующие в пределах Большеземельской тундры на восток до Урала, на север до Пустозерска и даже до Ледовитого океана. Они делились на самоедов Ижемского ведомства и Усть-Цилемского и на несколько родов: Хатанзейский, Валейский, Ванюта и Выучейский.

При устройстве первых церквей в самоедских приходах (Тиманском, Канинском и Колвинском) была учреждена строительная комиссия, в состав которой входили архимандрит Михаило-Архангельского монастыря Платон, игумен Никольского монастыря Филарет и чиновник IX класса Федоров. Комиссия местом построения церкви для самоедов Большеземельской тундры выбрала устье р. Колвы по нескольким причинам: 1) здесь на месте было достаточно строевого леса; 2) здесь проходили дороги, по которым идут на зимовку самоеды Ижемского ведомства; 3) здесь находились большие луга, необходимые причту для скотоводства. 22 сентября 1829 г. на этом месте водрузили крест (он существовал еще в конце XIX в.). Построена церковь на сумму, выданную по Высочайше утвержденному докладу Св.Синода из Государственного Казначейства. Престол освящен в честь свт. Николая, которого самоеды почитали до обращения в христианство. Строительство началось 11 июня 1830 г., закончилось в том же году. Иконостас был изготовлен в г. Архангельске, после его установки храм был освящен 25 марта 1831 г. В советские годы в его здании располагался сельский клуб. 22 мая 2007 г. восстановленный храм был заново освящён епископом Сыктывкарским и Воркутинским Питиримом.

Приписана походная церковь-палатка во имя свт. Николая, с иконостасом на полотне в 6 икон и Царских врат. Престол и жертвенник складные. Освящена 22 июня 1907 г., устроена по постановлению Архангельской Духовной Консистории в марте 1906 г.

Жертвователи: кафедральный протоиерей Иннокентий Попов пожертвовал капитал в пользу причта