Собор во имя святых, всехвальных и первоверховных апостолов Петра и Павла с приделами во имя святого благоверного князя Александра Невского и во имя святителя Павла Исповедника, патриарха Константинопольского был заложен в 1797 году в день коронации императора Павла I.

https://vk.com/wall-159713785_2587
https://lesnoyskitalets.livejournal.com/165853.html?thread=1448925

Храм строился на средства орловского дворянства. Из-за нехватки денег сооружение собора затянулось, и он был освящен только в 1841 году. В 1843 году была построена колокольня. Однако, в 1853 году богослужения в нем были прекращены из-за аварийности здания.

В 1861 году с разрешения Священного Синода собор был переименован, и главный престол был освящен в честь первоверховных св. апостолов Петра и Павла. В 1895 году собор был вновь отремонтирован и освящен чином полного освящения.

На службах в соборе в разные годы присутствовали императоры Александр II и Николай II, брат царя Михаил Александрович, Великий князь Сергей Александрович, его супруга Елизавета Федоровна, другие члены царской фамилии, выдающиеся деятели Русской Православной Церкви Иоанн Кронштадский, митрополиты Серафим (Чичагов), Флавиан (Городецкий), архиепископ Макарий (Гнеушев).

В соборе хранились знамена Орловской, Севской, Кромской, Елецкой, Ливенской, Малоархангельской дружин, подаренные храму после их возвращения с крымской войны.

Собор был закрыт в 1923 году, все ценности изъяты, а помещение передано областному архиву. Колокольня собора до войны служила пожарной каланчёй, парашютной вышкой и даже радиостанцией.

17 января 1938 года была утверждена новая комиссия по делам культа, в задачу которой входила подготовка материалов по закрытию храмов. В соответствии с проектом довоенной Генеральной схемы планировки Орла ею было принято решение о сносе Петропавловского собора. Областной архив переводится в здание Преображенской церкви. В 1940 году Петропавловский кафедральный собор был взорван.

После войны на месте храма долго были руины. В 1958 году на месте собора было построено здание для областной библиотеки. Некоторые элементы собора сохранились в архитектуре библиотеки. Открытие библиотеки состоялось 28 февраля 1958 года.