В писцовых книгах о землях и угодьях, принадлежавших причту, приход упоминался уже в 1600 г. В жизнеописании св. Афанасия Наволоцкого упоминается верхоледский священник Флор, который в 1647 г. был в числе священников, намеревавшихся освидетельствовать мощи св. Афанасия.

Известно, что 24 декабря 1774 г. сгорела приходская церковь. На сохранившемся антиминсе Никольского престола была подпись архиепископа Афанасия, сделанная в 1685 г. Вместо нее с 1776 г. строилась церковь во имя Живоначальной Троицы. В церкви было два храма, первоначально разделенные капитальной стеной. Один во имя свт. Николая, освящен в 1778 г., теплый. Второй во имя Св. Троицы, освящен 24.9.1780, холодный. В 1872 г. в трапезе на южной стороне устроен придельный зимний храм во имя свтт. Афанасия и Кирилла Александрийских. В 1877 г. стена между Никольским и Троицким храмами была удалена, храмы объединены.

Жертвователи: Татьяна Семушина пожертвовала 200 руб. на железо для церковной кровли; крестьянин Тимофей Леонтьевич Семушин в 1885 г. - колокол в 46 пуд. 36 ф.; солдатская вдова Матрена Голышева.

В церкви хранилась дарохранительница оловянная, весом 6 фунтов, и евангелие дестевое 1587 года, обложенное черным плисом, средник и фигуры евангелистов - серебряные под золотом, чеканные, по листам была надпись: "173 г. [7173 или 1665] декабря в 19 день положил в дом к церкви Николая Чудотворца на престол евангелие напрестольное с евангелистами Верхоледской слободки крестьянин Евдоким Григорьев Семушин по обещанию своему по своей души по своим родителям в вечное поминовение, а деньги дал за ту книгу свои, куплена книга на Москве, и тое книгу никому из церкви не продать не заложить. Книгу промежил Каргопольскаго уезду Кодлозерской пустыни строитель священник Алексий своею рукою подписал" (Цит. по: Краткое историческое описание приходов и церквей Архангельской епархии. Вып. 2 - Архангельск, 1895. - С. 130-133.).

Священники: Андрей Семенов Поромов, умер в 1762 г.; Кирилл Иванов Колчин до 1780 г.; Андрей Иванов Пороков; Сергий Козмин Владимиров, прослуживший в приходе 40 лет; Александр Евсигниев Петухов с 1850 г.; Илия Кондратьев Колчин до 1856 г.; Василий Иоаннов Шульгин; Павел Иаковлев Корелин до 1867 г.; Алексий Васильев Новиков 1867-1875 г.г.; Иоанн Филиппов Васильев 1875-1880 г.г.; Николай Бурневский до 1883 г.

Церковный староста: Тимофей Боровиков с 1887 г.