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