Начало строительства и первая деревянная церковь
15 декабря 1839 года крестьянин села Великовисочного Пустозерской волости Пётр Васильевич Дитятев обратился к епископу Архангельскому и Холмогорскому Георгию с ходатайством разрешить за счёт собственного капитала строительство в родном селе деревянной церкви взамен имевшейся ветхой деревянной часовни. В то время в Великовисочном насчитывалось 53 двора, где проживало 345 душ — 166 мужского и 179 женского пола. Не дожидаясь разрешения ни от Святейшего Синода, ни от Архангельской духовной консистории, Дитятев уже в 1840 году приступил к возведению храма. К 25 декабря 1842 года он доложил епископу о завершении строительства и просил оказать содействие в обеспечении церкви необходимым священническим имуществом и её освящении. В ответ епископ Георгий в письме управляющему Архангельской палатой государственных имуществ от 11 мая 1842 года ходатайствовал об освобождении крестьянина от преследования за самовольную постройку.
Священник Иннокентий Попов в своём рапорте от 8 августа 1844 года докладывал епископу Георгию: «Церковь в с. Великовисочном к освящению готова. Иконостас, иконы, ризы, одежда и все церковное украшение имеется, кроме книг, которые заказаны в Москву, а пока они из Москвы не пришли, просим позаимствовать их на время из Пустозерского прихода». Храм был деревянным, поставленным на каменном фундаменте, и освящён в 1845 году во имя Святителя и Чудотворца Николая. Это была одноглавая церковь с трапезной. Её длина составляла 5 саженей, ширина — 3,5 сажени, высота до крыши — 2 сажени. Крышу крыли тесом в два ряда. Над куполом церкви воздвигли восьмиконечный деревянный крест. Над папертью располагалась деревянная колокольня, вход на которую был устроен с крыльца церкви. Над куполом колокольни также возвышался восьмиконечный деревянный крест, обитый белой жестью. На колокольне висело два колокола: шестипудовый и шестифунтовый. Ограды вокруг церкви не было.

Чертеж плана на постройку церкви в селе Великовисочном.
В церковную опись Великовисочной Никольской церкви включили дом для причта с кухней, двумя жилыми покоями и двумя хлевами внизу. Это был дом, в котором ранее проживал великовисочный крестьянин Алексей Васильевич Дитячев (в документах встречается и написание «Дитятев»). Построив себе новый дом, старый он в ноябре 1844 года безвозмездно передал церкви. К храму приписали сенокосной земли на 174 воза. В реке Виска и ближайших озёрах причту разрешили вылавливать рыбы «столько, сколько им будет достаточно на 12 душ».

Чертеж плана на постройку церкви в селе Великовисочном.
Образование Великовисочного прихода
Так был образован Великовисочный приход, к которому, кроме села Великовисочного, отошли деревня Лабожское, стоявшая на реке Печоре в 9 верстах от приходской церкви, и выселки: Сульский – в 50 вёрстах и Индигский – в 120 вёрстах (по зимнику) в Тиманской тундре, ранее приписанные к Пустозерскому приходу. Позднее к Великовисочному приходу приписали деревни Пылемец, Тошвиска и выселок Курбас, находившиеся в 20 верстах от церкви.
В 1862 году при Великовисочной Никольской церкви открылось сельское приходское училище. В 1870 году в приходе учредили попечительский совет. Решением прихожан на трёхлетний срок избрали: местного священника Григория Легатова – председателем, а великовисочных крестьян Дмитрия Ивановича Суслова, Петра Васильевича Дитятева и Василия Фёдоровича Шалькова – членами совета. Прихожане также утвердили список лиц, имевших право участвовать в общих собраниях попечительства. В этом списке значилось 34 фамилии прихожан Великовисочного прихода.
Вторая Никольская церковь, колокольня и ограда
Первая церковь, построенная на средства Петра Васильевича Дитятева, оказалась мала для увеличившегося числа прихожан. В 1873 году на средства великовисочного крестьянина Николая Петровича Дитятева была возведена новая деревянная Никольская церковь. Она стала пятиглавой, построенной в виде корабля. На главах её возвышались восьмиконечные деревянные кресты. Освятил храм местный приходской священник Григорий Легатов. Позднее церковь снаружи обшили тёсом. В 1885 году вместо старого иконостаса в церкви устроили новый, стоивший 2000 рублей. Из этой суммы 1000 рублей пожертвовал Николай Петрович Дитятев, 800 рублей – великовисочная крестьянка Агриппина Кононова и 200 рублей – разные лица.
В 1879 году на средства приходского крестьянина Алексея Васильевича Дитятева в селе Великовисочном, в 7 саженях от Никольской церкви, построили высокую деревянную колокольню на каменном фундаменте. Тем же жертвователем для этой колокольни был пожертвован колокол весом 51 пуд 30 фунтов. Вокруг церкви и колокольни возвели деревянную решётчатую ограду.
Причт, прихожане и материальное обеспечение
На 1 января 1895 года в Великовисочном приходе всего состояло 862 прихожанина, в том числе 405 мужского и 457 женского пола; из них оседлых ненцев насчитывалось 40 (20 мужского и 20 женского пола). Средствами к содержанию церкви служили: проценты с капитала в 1000 рублей, пожертвованного Алексеем Васильевичем Дитятевым; суммы кружечно-кошелькового сбора (до 25 рублей); прибыль от продажи свечей, которых ежегодно продавали до 4 пудов; а также суммы приходского попечительства.
По данным за 1895 год, причт (священник и псаломщик) ежегодно получал жалование от казны 155 рублей, дохода до 100 рублей, процентов от капитала, пожертвованного крестьянином Алексеем Дитятевым – 45 рублей, и рыбных угодий на 20 рублей; кроме того, вместо пахотной земли от крестьян ежегодно в пользу причта поступало 128 рублей.
По имеющимся сведениям, священниками Великовисочного прихода с 1846 по 1895 год служили:
- Терентий Мелентиев (с 1846 года),
- Дмитрий Костьлев (с 1852 года),
- Григорий Легатов (с 1869 года),
- Андрей Костьлев (с 1880 года),
- Платон Кулаков (с 1883 года),
- Павел Таратин (с 1888 до 1895 года).
По ходатайству священника Великовисочного прихода Сергея Попова указом Архангельской духовной консистории от 16 января 1904 года разрешили произвести ремонт Никольской церкви. Кроме средств, пожертвованных прихожанами в сумме 500 рублей, на ремонт причту разрешили израсходовать из имеющихся в церкви свободных средств 200 рублей и до 200 рублей, вырученных от продажи свечей. В 1904 году в Никольской церкви поставили новые печи, исправили полы, а в паперти устроили новые; потолки, стены и полы покрасили масляной краской. На следующий год от церкви до колокольни проложили деревянные мостки.
В 1907 году на средства крестьян Великовисочного сельского общества в селе построили новый деревянный священнический дом. В 1908 году Никольскую церковь покрыли железной крышей, а в 1910 году церковь и колокольню снаружи окрасили белой краской.

План и фасад на постройку причтового дома в селе Великовисочном.
В 1909 году по ходатайству крестьянина выселка Курбас Великовисочного сельского общества Пустозерской волости Василия Петровича Попова, занимавшегося промыслами на Новой Земле, на его средства указом Архангельской духовной консистории от 13 апреля 1907 года в выселке Курбас построили деревянную часовню, которую приписали к Великовисочному приходу.
По сообщению заведующей сельским музеем З.А. Шальковой, в 1931 году в здании Никольской церкви разместили сельский клуб, а в 1950-х годах здание бывшей церкви было разобрано. В августе 2001 года на её месте установили памятный деревянный крест.