В сохранившихся в Архиве Министерства Юстиции писцовых книгах 1660 - 1670 год, выданных Новосельским попам Агею Михайлову и Афанасию Агееву сообщалось, что в селе Новоселках на речке Кутра имеется деревянная церковь во имя Пречистой Богородицы Казанской. При церкви 2 попа, просвирня. На церковной земле 2 двора бобылей питаются от церкви Божией. Имелись пашни, паханные церковные «средние земли» - 11 десятин в поле, да под кладбищем - 1 десятина, сена 50 копен. Из этой краткой выписки видно, что в Новоселках по какому-то случаю была построена новая Казанская церковь, и она получила особый земельный надел. Более подробные сведения о населении и церквах села Новоселки имеются в писцовых книгах Муромских дворцовых волостей 1676 года, в которых Новоселки значились «Государевым пашенным селом». Храм построен на средства приходских людей и был богато украшен иконами. Священствовали на тот период там попы Афанасий да Михаил. Вторая деревянная церковь во имя Николая Чудотворца была построена на средства попа Алексея Агеева. Да у той церкви два колокола. Была и третья деревянная церковь во имя Святого праведного Алексея, человека Божьего, построенная в 1650 году.Строение и всякая утварь были попа Афанасия Агеева.
Около церквей Пречистой Богородицы Казанской и Алексея, человека Божия, имелись ограды, покрытые деревянными пластинами. На церковной земле располагались дворы попов, место дворовое пономарское, просвирни да два - бобыльских двора. Всего в Новоселках числилось 48 дворов крестьянских и десять бобыльских дворов.
В состав Новосельского прихода, в то время как видно из окладных книг 1676 года, входили еще две деревни: Лобково – в ней 24 двора крестьянских и 2 - бобыльских (на 1896 год - 57 дворов) и д. Плотникова - в ней 2 крестьянских и один - бобыльский.
Таким образом, в последней четверти XYII века в Новоселках были три деревянные церкви, а село значилось дворцовой вотчиной. В XVIII и XIX столетиях Новоселки становятся уже помещичьим селом и принадлежали сначала графини Разумовской, а потом графу Гудовичу. По освобождению крестьян от крепостного права и после смерти графа А.Г. Гудовича, его имение поступило во владение его дочери А. А. Трубецкой - жены князя Н.И. Трубецкого.
Грамота, данная в 1802 году на построение каменного храма, упоминает только о пришедшей в ветхость деревянной церкви в честь Казанской иконы Божией Матери. О других церквах на тот период ничего неизвестно.
В 1802-10 гг. устроен в Новоселках каменный храм на средства главным образом зажиточного крестьянина Якова Вавилова. В новом храме устроено два престола: главный - в честь Казанской иконы Божией Матери, а в трапезе - во имя Архангела Михаила. В 1849-53 гг. трапеза была значительно расширена, и построена новая каменная колокольня и добавлен еще престол в честь Святой великомученицы Екатерины. Утварью, ризницей, св. иконами церковь снабжена была достаточно. В иконостасе холодной церкви сохранились без изменений иконы, написанные при постройке каменного храма в 1809 году. Из них особенно чтимы прихожанами иконы Спасителя и Казанской Божией Матери. В теплой церкви древностью отличались иконы Спасителя Иисуса Христа, Казанской и Тихвинской Божией Матери и Алексия – человека Божия. Храм построен на краю откоса, на месте бывшей деревянной церкви, пришедшей в негодность.
Любопытно то, что для написания икон во вновь строившемся храме храмоздателем Вавиловым был куплен у помещика д. Ишутина крепостной живописец Самарин, который в течение двух лет занимался работой, ведя все время строгую благочестивую жизнь. По окончании работ он был отпущен Вавиловым на волю.
Причта при церкви по штату было положено: священник, дьякон и псаломщик. На содержание их получалось из разных источников около 900 руб. в год. Дома у членов причта были собственные на церковной земле. План и межевые книги на эту землю имелись. Приход состоял из села Новоселок и деревень: Лобково и Лесниково. В коих по клировым ведомостям числилось 303 двора, 907 душ мужского пола и 1140 женского. Из них раскольников было 21 душа.
В Новоселках имелась начальное народное училище, открытое 20.02.1868 года, где учительствовал местный священник Гаврила Алексеевич Валединский с вознаграждением от земства 65 рублей в год. Обучение проводилось в доме учителя Валединского. И только в 1898 году было построено земством новое кирпичное здание. Преемником учителя стал его сын Сергей Гаврилович, который учительской работе посвятил всю свою сознательную жизнь с 1880 по 1923 год. Умер в декабре 1924 года.
Надо отметить, что в конце XIX столетия благочинным третьего Новосельского округа Муромского уезда был потомственный дворянин священник Гавриил Алексеевич Валединский, затем его в 1898 году сменил Павел Смирнов. Это подтверждается церковными метрическими книгами, сохранившимися до наших дней (Вачский районный архив Загса).
В 1896-1917 гг. священником Новосельской церкви был Иван Иванович Покровский (зять Гавриила Валединского), псаломщиками: Гаврила Покровский, Николай Левитский дьяконами: Евгений Преображенский, Григорий Знаменский.
В 30-х годах прошлого века началось разрушение храма, растаскивание церковной утвари, икон. В бывшем здании храма размещался склад. После проведения капитального ремонта там был обустроен сельский клуб. В 30-х годах прошлого столетия в Новосельском приходе служил священник Мраморов Михаил Иванович, которого арестовали 2.11.1937 года и в этом же году 2 декабря его расстреляли.
Двенадцатого сентября 2012 года для новосельцев и жителей района произошло знаменательное событие, связанное с тем, что в храме Казанской иконы Божией матери Владыка Варнава - епископ Выксунский и Павловский совершил Великое освящение престола в служении всего духовенства благочиния. Было совершено богослужение, крестный ход, окропление святой водой помещения, затем отслужили праздничную литургию. В храме новая утварь, установлены престол и высокий иконостас. Пол там с зеркальным блеском. Вокруг храма смонтирована кованая изгородь, площадка вокруг церкви выложена брусчаткой.
Материал из книги: Г.А. Арефьева и др. Наша история. Описание церквей и приходов Вачского края XVI-XXI в. Приложение. Книга четвертая. - Вача: ВыксаПолиграфИздат, 2010. Книга памяти жертв политических репрессий Вачского района Нижегородской области. Составитель О. Михеева. Н. Новгород. «БИКАР», 2010 г.