В городе было два приходских храма - Никольский собор и Ильинская кладбищенская церковь, и три монастырских храма - каменный Ильинский, деревянные Вознесенский и Никольский в основанном в 1855 году Пророко-Ильинском женском монастыре. К сожалению, в советское время все монастырские храмы были снесены.
Уже в середине XVII века в Мензелинском остроге была деревянная церковь. Именно на том месте, где она стояла в начале XIX века был построен трехпрестольный каменный Никольский собор. Приделы были освящены в честь чудотворной Смоленской иконы Божьей Матери и во имя Преподобного Феодосия Тотемского. Строительство собора началось в 1807 году, а главный престол освятили в 1813. Соборы уездных городов обычно строились за казенный счет. Но храм в Мензелинске построен, в основном, на средства, предоставленные по обету отставным унтер-офицером Матвеем Дмитриевичем Ситниковым, который несколько лет собирал деньги, обходя пешком всю Россию.
В 1878 году собор сильно пострадал от пожара, и в 1880-1890 гг. был реконструирован на средства елабужского купца и, одновременно, крупного помещика Мензелинского уезда Ивана Григорьевича Стахеева. Никольский собор представляет собой прекрасный образец стиля ампир. К сожалению, утрачена высокая пятиярусная колокольня. Собор имеет оригинальную объемно-планировочную композицию -центральный неф вместе с апсидой вынесен несколько вперед. Входы с западного, южного и северного фасадов украшены портиками дорического ордера. Центральный объем увенчан цилиндром большого диаметра с двумя рядами проемов, перекрытым полусферическим куполом с главкой на глухом барабане. Трапезная представляет собой одноярусное продолговатое сооружение с пятью высокими прямоугольными оконными проемами. Колокольня утрачена. Памятник архитектуры в стиле классицизм.