В 1836 году был построен каменный храм Рождества Пресвятой Богородицы с приделами во имя Архистратига Михаила и Николая Чудотворца.
В 1930-х гг. он был закрыт и часть его разобрали на стройматериалы для строительства школы. Другую часть церкви приспособили под больницу, сделав к ней дополнительные пристройки.
29 августа 2007 года состоялось освящение нового каменного храма во имя Рождества Христова, построенного на месте бывшего каменного храма во имя Рождества Пресвятой Богородицы.
С востока к четверику примыкает полукруглая апсида, рядом с которой находятся старинные захоронения, в том числе Петра Николаевича Дурново — государственного деятеля Российской империи (министра внутренних дел (1905-1906), представителя дворянского рода Дурново).
Источник: Информация с диска «Православные храмы земли Пензенской»
Существовавшая ранее Рождество-Богородицкая церковь в селе Деревянном Колышлее построена была в 1816 г. на средства прихожан, деревянная, крепкая. Престолов в ней, кроме главного, три: в правом приделе – во имя Архангела Михаила, в левом – во имя святителя и чудотворца Николая Мирликийского и под колокольней – в память сошествия Св. Духа на апостолов; последний престол построен в 1841 г. на средства г. Симанского; настоящая и приделы холодные, а под колокольней церковь теплая.
Есть земская школа; церковно-приходское попечительство с 17 июля 1892 г. При церкви имеется отделение духовно просветительного союза, открытое в 1886 г., помещается оно в трескинской земской школе, где производятся в праздничные дни чтения. При отделении открыта в 1893 г. бесплатная библиотека с книгами исторического и духовно-нравственного содержания для бесплатной раздачи для чтения прихожанам и, сверх сего, в 1895 г., с разрешения г. губернатора, земством для той же цели открыто при Трескинской школе образцовая библиотека с книгами разного содержания.
Земли при церкви усадебной около 3 дес., пахотной 33 дес.
В приходе есть домовая каменная церковь во имя Святого Благоверного князя Александра Невского, построенная в 1867 г. на средства г-жи Тапорниной; в этой церкви приходский причт служит еженедельно в пяток.
У священника дом церковный, деревянный, застрахован. Жалованья от казны причту 235 руб. 20 коп., и, кроме того, духовенство пользуется процентами с принадлежащего церкви капитала. Священник Алексей Князевский и псаломщик Михаил Дубасов.
Прихожан при церкви: дворян, купцов, мещан, военных и крестьян обоих полов душ 2639; дворов 541. В приходе три сельца: Полянщина, Каменка и Куршевка.
«Краткие сведения о церквах Саратовской епархии, существующих при них причтах и о прихожанах»: приложение к «Саратовским епархиальным ведомостям» № 8–11, 17–24 за 1895 г.
