Впервые церковь в “приселке” Тростино (Трестино), бывшем в то время вотчиной московского Новинского Введенского монастыря, упоминается в 1617 г., когда здесь стояли два построенные монастырем деревянных храма – Никольский (летний) и во имя св. вмц. Параскевы Пятницы (зимний). В конце 80-х гг. XVIII в. взамен деревянных был возведен каменный пятиглавый храм с шатровой колокольней, освященный в 1790 г. Храм имел три престола: в холодном четверике – во имя свт. Николы, в теплой трапезной; правый – во имя прп. Геннадия Костромского и Любимоградского и св. вмц. Екатерины; левый – во имя св. вмц. Параскевы Пятницы (первый и третий престолы перенесены из деревянных церквей, а второй, по-видимому, был устроен храмоздателями в честь своих небесных покровителей). Главная святыня храма – местночтимый, по преданию явленный, образ свт. Николы. В 1901-1921 гг. настоятелем церкви служил один из самых выдающихся священнослужителей Костромского края XX в. – протоиерей Павел Федорович Острогский (1877-1937 гг.).
Храм в Николо-Трестине относится к числу немногих церквей района, избегших в советское время закрытия... "Николаевская церковь села Трестина, устроенная в 1790 году иждивением прихожан, зданием каменная, с таковыми же колокольней и оградою. Кладбище в ограде при церкви. Престолов три: в летнем храме - во имя святителя Николая чудотворца; в зимнем: северный - во имя преподобного Геннадия, Костромского и Любимоградского чудотворца, и святой великомученицы Екатерины; южный – в честь святой великомученицы Параскевы Пятницы. Из местных святынь замечателен образ святителя Николая, по местному преданию, явленный.
Раньше на том месте, где теперь село, было болото – трясина. Тут явился святитель Николай на сосне одному старичку – крестьянину и осушил болото. Была построена церковь, и образовавшееся новое село названо «Трестино» от слова «трястись», трясина. Образ был долгое время на испытании в Ипатьевском монастыре и только в 1889 г., благодаря хлопотам прихожан и госпожи Мичуриной, он был возвращен в приходскую церковь. Имеются при церкви попечительство и общество трезвости. Расстояние от Костромы 9 верст. Ближайшие церкви: с. Минского в 3 версты, с. Куликова в версту и с. Петровского в 4 верстах. Причт: священник и псаломщик. Земли причтовой: лесной 10 десятин, пахотной 20 десятин, луговой 1 десятина, а остальная под большой Красносельской дорогой и болотом. Прихожан - 524 душ мужского пола и 600 женского. Главное занятие прихожан – земледелие, и только свободные в семье люди и безземельные уходят в город и поступают там на фабрики, в услужение. В приходе 14 селений; дальнее в 5 верстах от церкви. Школ в приходе две: одна церковно-приходская в самом селе, другая земская в дер. Давыдовском (5 верст)"...
По информации с сайта прихода: nikolo-trestino.prihod.ru