Приходу, по гражданско-административному делению, соответствовала "Патрикеевская волость", в 60 верстах от г. Архангельска. Приход назывался по реке Мудьюге. В памятной книге 1822 г. было записано предание о том, что на реку Мудьюгу пришли 3 родных брата, бежавших из Новгорода от гнева Иоанна III Васильевича. Здесь, видимо, уже жили чудские племена. Когда появились еще пришлые люди и население увеличилось, была проведена перепись, при этом трем братьям дали прозвища: Безбородый, Морозов и Негодяев. И долгое время земли, принадлежавшие братьям, назывались Безбородовской, Морозовской и Негодяевской.

По благословению Преосвященного Варлаама, митрополита Новгородского и Великолуцкого, была построена церковь во имя свт. Николая Мирликийского, которая сгорела в 1597 г., причем это была не первая церковь, предыдущая также была в честь свт. Николая. В 1599 г. построена новая церковь, существовавшая до 1764 г., когда по ветхости была заменена другой, тоже Никольской. Новая церковь была шатровая, холодная, деревянная. Освящена 6 декабря 1764 г. 18 июля 1890 г. было дано разрешение епархиального начальства на капитальный ремонт церкви, она была поднята на 2 ряда природного белого камня.

Кроме Никольской, в приходе была каменная Успенская церковь, которой предшествовали 3 деревянные того же имени. Первая из них к середине XVII в. обветшала и в 1650 г. была заменена новой, по благословению Преосвященного Никона, митрополита Новгородского и Великолуцкого. Сгорела 17 октября 1774 г. Третья Успенская церковь, теплая, шатровая, построена по благословляющей грамоте Преосвященного Вениамина от 28 февраля 1778 г.. Сгорела до основания 7 сентября 1871 г. по неосторожности сторожа.

В 1872 г. решено было строить каменную церковь с главным престолом в честь Успения Богородицы и с двумя приделами в трапезе - южный в честь Введения во храм Божией Матери и северный во имя блаж. Василия, Христа ради юродивого. Проект и план составил губернский инженер Васильев. Придельные теплые храмы были освящены в 1878 г. Главный Успенский храм освятили 22 сентября 1884 г. Большое участие в строительстве этого храма приняли бывший мудьюжский прихожанин, переселившийся в г. Архангельск, купец Иван Иванович Антуфьев (пожертвовавший 1000 руб.) и прихожане, собравшие по подписке между собой 628 руб. 50 коп.

Важнейшей святыней прихода была древняя храмовая икона свт. Николая, украшенная серебряной под золотом резьбой и считавшаяся чудотворной. Без этой иконы ни один дом, ни один корабль или шхуна не строились, каждый крестьянин, отправляясь в дальний путь или возвращаясь из плавания, совершал молебен перед иконой. К образу с давних времен был привешен четырехконечный с яблоками серебряный крест с мелкозвенчатой цепочкой, в котором хранились мощи трех святителей и прав. Артемия. По преданию, крест был привешен усердием архимандрита Сийского монастыря Германа. Впоследствии крест хранился в дарохранительнице св. престола.

Приписная Иоанно-Богословская церковь: находилась на Мудьюжском острове близ Мудьюжского маяка в 6 верстах от приходских церквей. Построена в 1882 г. по просьбе командира над Архангельским портом князя Ухтомского и по благословению Преосвященного Нафанаила II. Церковь была деревянная, очень маленьких размеров. Некоторые из предметов церковной утвари были пожертвованы архангельскими офицерами морского ведомства, дарохранительница изготовлена из серебряных офицеркских эполет. Богослужения совершались причтом Соломбальского собора 2 раза в год: 8 мая (апостола и евангелиста Иоанна Богослова) и 26 сентября (преставление апостола и евангелиста Иоанна Богослова).

К 1 января 1894 г. прихожан было 808 мужчин и 959 женщин. В 1849 г. открыто сельское училище. Церковно-приходское попечительство образовано 22 октября 1872 г. В Мудьюге работало шкиперское училище, причем окончившие курс сдавали экзамен при Архангельском порте и получали дипломы, дававшие право управлять морскими парусными судами.

Жертвователь: архангельский купец и почетный гражданин Иван Иванович Антуфьев пожертвовал 2 серии (денежные процентные билеты) по 50 руб. каждая в пользу церкви и 2 такие же серии в пользу причта.

Священники: Иоанн Нечаев до 1695 г. (поступил в монашество с именем Иосиф и скончался в должности архимандрита Сийского монастыря, где и был погребен); его сын Матфий Иванов Нечаев с 1695 г. (тоже поступил в монашество с именем Митрофана и скончался архимандритом того же монастыря); сын Матфия Иоанн Нечаев (по причине вдовства был пострижен в Соловецком монастыре в монашество с именем Иларион, по болезни уволен в Мудьюгу, где и умер); его сын Алексий (в 1743 г. рукоположен во священника и служил 75 лет); одновременно с ним служил протоиерей Максим Иванов Резанов 1761-1764 г.г.; протоиерей Иосиф Нечаев 1818-1822 г.г. (утонул); Петр Стефанов Варфоломеев 1822-1827 г.г.; Иоанн Семенов 1827-1830 г.г.; Андрей Прокопьев Едович 1830-1841 г.г.; Иоанн Федорович Розанов 1855-1.4.1856; Гавриил Богоявленский 1856-1859 г.г.; Стефан Михайлов Афанасьев 1859-1872 г.г.; Александр Алексиев Зуев 1872-1874 г.г.

Староста: крестьянин Александр Корконосов с 1884 г.