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