С XVI века главным храмом Брянска являлся Покровский собор, находившийся в брянском кремле. В 1798 году указом Святейшего Синода соборный статус был придан Преображенскому храму (1694-1697 гг.) упраздненного в 1766 году Спасо-Поликарпова монастыря, переименованному в связи с этим в Покровский.

В 1862 году храм был разобран, и на его месте возведен новый собор, строительство которого велось более трех десятилетий (в 1876 году был освящен правый придел во имя свт. Николая Чудотворца, в 1879 году — левый, во имя мч. Иоанна Воина, в 1897 г. — главный престол в честь Преображения Господня). С 1920 года, после образования Брянской епархии, Покровский собор стал кафедральным, но уже в 1924 году он был закрыт и разорен. Здание, использовавшееся как клуб и антирелигиозный музей, сильно пострадало в Великую Отечественную войну, а в начале 1960-х годов его снесли. В 1968 году была взорвана и колокольня. Сейчас на этой территории стоит киноконцертный зал «Дружба», а в память о соборе на его месте возведена часовня в честь Покрова Пресвятой Богородицы, освященная в 2002 году.

С 2002 года начались переговоры с администрацией о месторасположении будущего кафедрального собора. В 2004 году епархии был выделен земельный участок под строительство собора — в историческом и географическом центре Брянска, рядом с соборным храмом в честь Воскресения Христова, на территории, некогда принадлежавшей древнему Воскресенскому девичьему монастырю. С этого времени на месте будущего алтаря неоднократно совершалась Божественная литургия и другие чинопоследования под открытым небом.

30 мая 2005 года по ходатайству епископа Брянского и Севского Феофилакта приснопамятный Святейший Патриарх Алексий II благословил строительство кафедрального собора в честь Живоначальной Троицы, а несколько позже — соборного духовно-просветительского комплекса. В том же году образован региональный общественный фонд «Брянский кафедральный собор», начались проектные и исследовательские работы.

С 2010 года по ходатайству Святейшего Патриарха Московского и всея Руси Кирилла работы велись преимущественно благодаря помощи ОАО «Газпром», а также на средства московских благотворителей и жителей Брянщины. В минувшие годы за богослужениями во всех храмах епархии возносилось особое прошение «О благотворителях, благоукрасителях, жертвователях и строителях Брянского кафедрального собора». Еженедельно в Воскресенском храме у мощей преподобного князя Олега Брянского священнослужителями епархии читался акафист Святой Живоначальной Троице. Во всех храмах епархии были установлены кружки для сбора пожертвований на возрождение Брянского кафедрального собора.

В 2007 году, в праздник Сретения Господня, был заложен и освящен фундамент нижнего яруса будущего кафедрального собора.

23 мая 2010 года, в праздник Святой Троицы, епископом Феофилактом была совершена первая Божественная литургия в нижнем ярусе Брянского кафедрального собора. Затем Божественная литургия в нижнем ярусе собора совершалась в день празднования Собора Брянских святых, на Рождество Христово и на Пасху.

В 2011 году был завершен основной этап строительства кафедрального соборного комплекса: Свято-Троицкого кафедрального собора, колокольни «Пересвет» и деревянного храма в честь новомучеников и исповедников Брянских. В том же году освящены престолы нижнего яруса собора и храма во имя новомучеников и исповедников Брянских.

24 июня 2011 года, в день празднования в честь иконы Божией Матери «Достойно есть», на соборную колокольню «Пересвет» были воздвигнуты глава и крест.

26 июня 2011 года, во время своего визита в Брянскую епархию, кафедральный собор посетил Святейший Патриарх Московский и всея Руси Кирилл.

16 декабря 2011 года под колокольней «Пересвет» был установлен бронзовый памятник преподобномученику Александру Пересвету, в 2012 году он был перемещен за ее стены.

24 мая 2012 года, в праздник Вознесения Господня и день памяти свв. равноапп. Мефодия и Кирилла, учителей Словенских (тезоименитство Святейшего Патриарха Кирилла), была совершена первая Божественная литургия в верхнем ярусе Брянского кафедрального собора, которую возглавил епископ Брянский и Севский Александр.

23 июня 2012 года в соборном кафедральном комплексе состоялось торжественное перенесение мощей преподобного благоверного князя Олега Брянского из соборного храма в честь Воскресения Христова в кафедральный собор во имя Святой Троицы. Церемонию перенесения и богослужение возглавил епископ Александр. Раку установили в центре верхнего яруса кафедрального собора.

К июню 2012 года завершена внутренняя и внешняя отделка собора и колокольни, высота которой составляет около 70 метров, завершается благоустройство территории. Площадь нижнего яруса Собора составляет 1000 м2, верхнего яруса — 882 м2.

1 июля 2012 года Святейший Патриарх Московский и всея Руси Кирилл совершил чин великого освящения престола верхнего яруса кафедрального собора.