1 октября 2003 года начато строительство нового храма. Епископом Барнаульским и Алтайским Максимом (Дмитриевым) был освящен закладной камень, после чего за работу взялись строители. Освящен новый храм в честь Покрова Божией Матери 19 сентября 2004 года Епископом Барнаульским и Алтайским Максимом.
На территории Ельцовки стояла деревянная церковь во имя Покрова Пресвятой Богородицы, построенная в 1888 году. Земли при ней не было. В состав прихода Кузнецкого уезда входили: деревня Аныштаиха – 12 верст, Новокаменка – 14 верст, заселки Бедрепский – 15 верст, Пилинский – 7 верст. Причта по штату: священник и псаломщик. Содержание жалованья от прихожан 400 рублей, готовое помещение и доходы от треб. Прихожан обоего пола насчитывалось – 3000 душ, раскольников, обособленных порядком - 61 душа. Расстояние от Томска в 550 верст, от благочиния в 120 верст. Было 4 часовни. Школа грамоты открыта в 1895 году, помещалась в церковной сторожке. Учительницей была жена местного священника, окончившей курс в женской гимназии. Она получала жалование в 150 рублей в год. Кроме этого в приходе было еще 4 школы грамоты: в деревне Ново-Каменской, Бедрепской, Калтыкской, Аныштаихинской, которые содержались на средства местных жителей. Молитвенные дома были в деревнях: Калтык, Аныштаиха, Черемшанка, приписная церковь в деревне Новокаменка, во имя святых Апостолов Петра и Павла. Попечительство с 1895 года.