При учреждении Орловской губернии в 1778 г. под кладбище было отведено новое место за городом. Церкви на кладбище не было 50 лет и лишь указом Орловской духовной консистории от в 1823 г. разрешено было построить церковь каменным зданием на пожертвования. Новопостроенная каменная церковь во имя Живоначальной Троицы была освящена в мае 1828 г. Служение в новопостроенной церкви началось с сентября того же года. Церковная паперть в 1849 г. была вымощена камнем, между колонами вокруг церкви сделаны деревянные решетки. Со временем церковь была значительно расширена. В 1864 г. церковь начали реконструировать. Освящение перестроенного храма было совершено в 1867 г.
Первоначально Троицкая колокольня состояла из двух столбов с перекладиной. В 1838 г. столбы эти обветшали и вместо них поставлены были новые дубовые, с устройством над ними деревянной кровли, и в таком оставалась до 1850 г. В 1851 г. начался сбор пожертвований на строительство каменной колокольни. Постройка колокольни была окончена в 1854 г.
После революции Троицкая церковь стала обновленческой. В 1929 г. дом причта был отобран у церковной общины и заселен жильцами. Зимой 1930 г. были сняты колокола. Церковь работала еще несколько лет и в середине 1930-х г.г. была закрыта. К началу Великой Отечественной войны Троицкая церковь уже не работала. Последняя в городе Орле действующая церковь - Воскресения Христова на Афанасьевском кладбище - была закрыта в 1941 г.
В 1944 г. Троицкая церковь была передана церковной общине в бесплатное пользование. В 1979 г. был расписан алтарь. В 1980 г. в алтаре был устроен отдельный вход с северной стороны и небольшая пристройка, «паномарка». В 1983 г. была проложена 35-метровая сеть водоснабжения с вводом в северный придел храма. Для слива использованной воды был устроен колодец.
К 1990 г. на первом этаже дома причта был устроен храм в честь святителя Иоанна Златоустого. На втором разместилась воскресная школа и библиотека. Школу открыли в 1991 г. В середине 1990-х г.г. при Троицкой церкви появилась часовня.
В 2011-2013 г.г. проведены реставрационные работы по монументальной живописи на своде купола - укрепление штукатурного основания, удаление цементных, гипсовых вставок, дезинфекция, заделка трещин, восполнение штукатурного основания, укрепление красочного слоя, укрепление мелких шелушений красочного слоя, удаление емчуги, удаление потемневшей олифы, въевшейся копоти, пропитка грунта, тонировки и воссоздание живописи, защитное покрытие.
В 2013 г. при проведении в Свято-Троицкой церкви реставрационных работ историки и краеведы обнаружили, что некоторые могилы были разграблены в 1930-1950-х г.г. Сотрудники Института археологии РАН обследовали мемориал и собрали поруганный прах воедино. В 2014 г. в Свято-Троицком храме Орла был торжественно открыт воссозданный склеп генерала Алексея Петровича Ермолова и членов его семьи. Мемориал прославленного военачальника был отреставрирован и приведен в близкий к первоначальному вид.
На воинском кладбище, расположенном рядом с церковью похоронены воины, павшие в боях за освобождение города Орёл в 1943 г.
Информация с сайта Министерства культуры Российской Федерации, http://www.mkrf.ru
