Население деревни Окуловка и окрестных деревень принадлежали прежде к приходу Перетновской церкви. Но после строительства железной дороги и быстрого роста числа жителей появилась необходимость в строительстве собственной церкви.
В 1865 г. в Окуловку из села Мшенцы бывшего Валдайского уезда (теперь Бологовский район) была перевезена деревянная церковь Рождества Богородицы, существовавшая там с 1789 г. Эта деревянная церковь действовала в Окуловке вплоть до строительства в 1901 г. каменного храма.
Все эти 35 лет в церкви служил священник Михаил Петрович Тихомиров (Новг. епархиальные ведомости. 1901г. С. 875—883) Среди священников Окуловской церкви упоминается также Иоанн Маркович Крылов (Памятная книжка Новгородской губернии на 1875 г.)
25 июня 1900 г. Окуловку посетил архиепископ Новгородский и Старорусский для освящения закладного камня будущего каменного храма.
Каменная церковь строилась во славу свт. Николая, но освящена была в честь св. блгв. вл. кн. Александра Невского. На строительство храма около 80 тыс. руб. пожертвовали окуловский купец Иван Зубов и церковный староста Косма Егоров. Герцог Лейхтенбергский (его усадьба была в имении Горы) подарил церкви копии с картин А. Иванова «Явление Христа Марии Магдалине» и «Беседа Христа с самарянкой» художника Мартынова.
Каменная церковь имеет длину с колокольней 18 саженей. На церкви был купол каменный, восьмерик и четыре малых по углам, на всех железные кресты с золочеными шарами. Колокольня была трехъярусная, высотою 12 сажень. Внутри церковь была оштукатурена и расписана орнаментом.
В 1908 г. по соседству с церковью была выстроена богадельня, по благословению Иоанна Кронштадтского, где содержались 12 старушек и 2 старика. Деньги пожертвовали купцы Соловьев, Самсонов и Зубов, а купчиха Говорова поднесла 95 аршин материи на форменные платья для богоделок. Отец Иоанн Кронштадтский прислал на открытие богодельни свой портрет с дарственной надписью.
В январе 1937 г. Президиум ВЦИК утвердил «Ходатайство трудящихся поселка Окуловка о закрытии церкви». К 20-й годовщине Октябрьской революции в церкви был открыт звуковой кинотеатр «Родина», на оборудование которого было затрачено 120 тыс. руб. После строительства в Окуловке нового кинотеатра «Экран» церковь была перестроена под детскую спортивную школу, при этом были разрушены своды, купола и колонны.
5 июля 1993 г. церковь передана Окуловской православной общине. Церковь была передана в ужасающем состоянии. По заключению комиссии износ здания составлял 100 %. Кровля текла, над алтарной частью вообще отсутствовала, система отопления неисправна, котельная демонтирована, деревянные полы частично сгнили, частично сняты, стекла в окнах выбиты почти все. Разорение полное. 17 декабря 2009 г. было завершено восстановление колокольни храма на средства благодетеля р. б. Сергия из г. Санкт-Петербург с посильным участием жителей г. Окуловка.
http://vn-eparhia.ru/zhurnal-sofiya/135-zhurnal-sofiya-2-2010/460-palomnichestvo-po-svutum-mestam-okulovskogo-raiona