Церковь Николая Чудотворца в селе Старое (историческое название — Старое Село) впервые упоминается в окладной книге 1691 года как храм в Авнежской волости Вологодского уезда. Каменное здание церкви было построено в 1744 году. Главный престол освящен во имя святителя Николая Чудотворца, архиепископа Мирликийского. Дополнительные престолы посвящены иконе Божией Матери «Страстная», Сретению Господню и Воспоминанию чуда Архистратига Михаила.
10 октября 1882 года состоялось освящение придельного храма во имя Николая Чудотворца. В 1900 году проводился капитальный ремонт нижнего теплого этажа храма, включавший каменные, печные и штукатурные работы. На торги, объявленные 17 апреля 1900 года при Покровской Кирилловской Слободской церкви, начальная сумма составляла 555 рублей 85 копеек по смете. В 1905 году церковным старостой на второе трехлетие утвержден крестьянин Евгений Чемин.
Приход храма исторически относился к Грязовецкому уезду Вологодской губернии. Село Старое расположено при реке, в местности, административно входившей в Старосельское сельское поселение Междуреченского района. Архитектурные особенности здания характерны для храмового строительства середины XVIII века в Вологодской губернии.
