Строительство нового православного храма для г. Мелеуза было начато в эпоху перестройки – в 1990 г. на месте большой Троицкой-Никольской церкви, снесённой незадолго до этого (здание существовало с ~1898 г., а до этого здесь стояла старая Троицкая церковь). В 1994 г. сооружение нового кирпичного храма, названного в память последней действовавшей церкви Мелеуза "Казанско-Богородским", было завершено. Храм 7-главый, с трёхъярусной колокольней. Архитектурный стиль – современная эклектика с отдалёнными восточно-романскими мотивами. К сожалению, здание строилось из некачественного тресканного "рыжего" кирпича, ныне оставленного "на обветривание". Подо всем зданием обширное служебное подцерковье. Во время строительства настоятелем служил о. Владимир Степанов (1990-97 гг.).
Ныне близ церкви ведётся строительство 2-х этажного кирпичного здания воскресно-приходской школы. В 2004 г. заменены кресты и купола. В 2002 г. для поддержки Покровского Эннатского мужского монастыря приходская Казанско-Богородская церковь была временно преобразована в монастырское Казанско-Богородицкое подворье. Святыни храма: мощи местночтимой святой блаженной Варвары Скворчихинской, чтимая икона вмч. целителя Пантелеимона с частицей его мощей, ковчег с более чем 100 частицами святых мощей и иные.
Историк Уфимской епархии Егоров П.В., добавления по современности иг. Симеона (Кувайцева) и о. Владимира Семавина.