Приход располагался на Зимнем берегу Мезенского залива и состоял из одного села Койденского. Село основали крестьяне д. Куи Архангельского уезда, вынужденные оставить родные места из-за постоянных набегов шведов в конце XVII - начале XVIII в.в. Первоначально село входило в Долгощельский приход, в селе имелась часовня в честь свт. Николая. Поскольку расстояние до приходского храма было большое, жители деревень Койды и Майды 13 августа 1840 г. ходатайствовали к Преосв. Георгию о разрешении построить в д. Койде вместо часовни деревянную церковь во имя свт. Николая и приписать ее к Долгощельскому приходу. Разрешение было дано Св. Синодом 18 ноября 1843 г. Строительство началось по храмозданной грамоте Преосв. Георгия от 17 декабря 1843 г. План был составлен архитектором Польманом. Построена церковь была без особых трудностей, поскольку в те годы доходы от промыслов были высокие. Особое усердие в сборе средств и в строительстве проявил крестьянин Иван Петрович Малыгин. В 1850 г. был образован самостоятельный приход. Престол во имя свт. Николая освящен 24 января 1851 г. епископом Варлаамом. Часть икон была куплена в Соловецком монастыре и Ануфриевском ските.

Часовни: в становище Кеды (20 верст от прих. храма), на о. Моржовце (60 в.) и в с. Койде.

В приходе особо чтились иконы: Тихвинская Божией Матери; храмовая икона свт. Николая Чудотворца; преп. Евдокии, в праздник которой, 1 марта, начинались промыслы по Зимнему берегу; Иоанна Богослова, ко дню памяти которого 8 мая промыслы заканчивались; Алексия, человека Божия и др.

Церковный староста: Василий Малыгин с 1887 г.