Храм в честь святителя Николая Мирликийского Чудотворца в селе Холмогоры был построен в 1809-1813 годах. Это каменное здание с тремя престолами: главным в честь свт. Николая (освящен 13.07.1813), придельным южным в теплой трапезе во имя Рождества Христова (освящен 23.05.1809) и северным - Рождества Иоанна Предтечи (освящен 24.06.1809). Церковь с колокольней в одной связи была возведена на средства бывшего прихожанина, московского купца Димитрия Васильевича Сорокина.
История прихода восходит к XVI веку, когда на территории Холмогор существовало четыре отдельных прихода: Троицкий, Рождественский, Никольский и Покровский. На Никольском посаде находилась деревянная Николаевская церковь, построенная в 1629-1631 годах, которая к концу XVIII века пришла в ветхость и перестала использоваться для богослужений. В октябре 1808 года при новой каменной Никольской церкви был учрежден самостоятельный причт, а Рождественский Нижнепосадский приход переименован в Никольский.
В 1871-1873 годах приходом временно заведовал причт Спасо-Преображенского собора, а в 1874 году он был присоединен к Троицкому приходу. В результате сокращения населения Холмогор из четырех исторических приходов образовался один, в котором осталось три церкви: Троицкая (главная приходская), Никольская (приписная) и Покровская (кладбищенская).
В советский период храм был закрыт. Возрождение духовной жизни началось в 1997 году с образования подворья Антониево-Сийского монастыря. В 1998 году был образован православный приход села Холмогоры. 9 июня 2015 года организован приход святителя Николая. С августа 2017 года храм вошел в состав архиерейского подворья Спасо-Преображенского собора села Холмогоры, куда также включены Спасо-Преображенский собор, храм 12 апостолов, храм во имя Святого Духа и территория бывшего Свято-Успенского женского монастыря.
Архитектурно храм представляет собой характерный для начала XIX века образец северного церковного зодчества. Композиция здания включает основной объем, трапезную и колокольню, объединенные в одну структуру. В декоративном оформлении использованы элементы классицизма, что отражает переходный период от барокко к классицизму в церковной архитектуре Русского Севера.