Первое здание Троицкой церкви с приделом Святого Дмитрия Ростовского и колокольней было освящено 19 октября 1694 года. К середине XIX века это здание обветшало и было разобрано в 1844 году. От первоначального комплекса сохранилась только Старотроицкая колокольня, сооружённая в 1689 году.
В 1845 году началось строительство нового здания церкви по проекту архитектора Константина Андреевича Тона. Строительство продолжалось 12 лет и завершилось в 1857 году освящением храма. Проект был типовым; аналогичные храмы были построены в Санкт-Петербурге, Сызрани и Петрозаводске.
В строительстве и благоукрашении храма активно участвовали местные купцы, включая семьи Носовых, Рощиных и Унжениных. Купец первой гильдии Иван Васильевич Лесников пожертвовал церкви святое Евангелие весом 35 фунтов (около 14,33 кг) стоимостью 1700 рублей, а также 15 000 рублей ассигнациями.
В 1878—1889 годах рядом с церковью была построена Новотроицкая колокольня высотой 66,5 метров в стиле башен Московского Кремля. В дореволюционное время на ней отбивали время суток.
В 1935 году церковь была закрыта и использовалась для различных хозяйственных нужд. В 1991 году здание возвращено верующим, и 12 июля 1998 года в храме возобновились богослужения. С 1999 года Троицкая церковь получила статус собора.
Архитектурно храм выполнен в русско-византийском стиле. В основе плана лежит греческий крест, под средокрестием которого возведён купол на восьмигранном барабане. Крест заключён в квадрат с выступающими ветвями. С востока здание завершается тремя апсидами, а на углах квадрата расположены четыре малые главы. Высота храма достигает 41 метра.
