Решение о его строительстве было принято в 1842 году городским обществом, стремившимся возвести кафедральный собор, соответствующий статусу губернского и епархиального центра. Для реализации проекта был выбран образцовый проект архитектора Константина Андреевича Тона, ранее использованный при строительстве Введенской церкви лейб-гвардии Семёновского полка в Санкт-Петербурге.
Закладка собора состоялась 3 июня 1845 года. Однако в 1850 году, на завершающем этапе строительства, произошло обрушение центрального купола, повлёкшее гибель четырёх человек. Это событие приостановило работы и потребовало пересмотра проекта.
Возобновление строительства произошло в 1858 году, но из-за финансовых трудностей и снижения общественного интереса работы вновь были приостановлены. Только в 1885 году под руководством городского архитектора Василия Васильевича Хабарова строительство было продолжено и завершено к 1889 году. Внутренняя отделка собора продолжалась до лета 1900 года, когда храм был официально освящён и открыт для богослужений.
Архитектурно собор представлял собой здание в русско-византийском стиле, характерном для проектов К.А. Тона. Он имел три престола: главный — во имя Святой Живоначальной Троицы, и два придела — святителя Николая Чудотворца и святого благоверного князя Александра Невского. Размеры собора составляли 42,6 метра в ширину и 59 метров в высоту, включая крест. Он был рассчитан на одновременное присутствие 2,4 тысячи молящихся.
В 1930 году, в период антирелигиозной политики советской власти, собор был закрыт. Первоначально здание использовалось под учебные мастерские, рассматривались планы по его переоборудованию в планетарий. Однако в 1934 году собор был полностью разобран, а на его месте был разбит сквер на Новособорной площади.
