Церковь построена в 1823-1828 годах на кладбище, основанном в 1778 году, на средства мирян. Среди жертвователей были губернатор, вице-губернатор, губернский архитектор, действительный статский советник П.А. Ермолов, многие другие орловцы и среди них дворник полковника С.М. Тургенева. В 1852-1854 годах возведена колокольня. В 1861 году у церкви, рядом с могилой своего отца П.А. Ермолова (1746-1832), был похоронен известный военачальник, генерал от артиллерии А.П. Ермолов (1777-1861).
В 1865-1867 годах на деньги, выделенные императором Александром II и также детьми генерала, по проекту архитектора В.С. Попова церковь была перестроена, расширена двумя приделами и соединена с колокольней. Под южным приделом устроен склеп семьи Ермоловых. В церкви установлен памятник — надгробные плиты П.А. и А.П. Ермоловым, а также четырехугольный медный пьедестал, на котором стояла чашка чугунной гранаты с лампадой под круглым стеклом. В 1897 году с разрешения министра внутренних дел склеп был расширен, и в нем похоронены сын А.П. Ермолова Клавдий Алексеевич и его жена Варвара Николаевна.
В 1930 году церковь была закрыта, вновь стала действовать с 1942 года. В 1953 году на стене южного придела был установлен барельефный памятник А.П. Ермолову (скульптор Б.Д. Бологов), а в 1997 году — мемориальная доска в память семьи Ермоловых.
При учреждении Орловской губернии в 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
