Крестительская церковь расположена на юго-западной окраине города на Крестительском кладбище, основанном в 1772 г., среди густо разросшихся кустарников и деревьев. В 1774-77 гг. построена каменная церковь во имя Иоанна Крестителя. В 1828 г. к ней пристроена трапезная с колокольней и двумя приделами во имя иконы "Всех Скорбящих Радость" и Казанской иконы Божьей Матери. В 1870 г. церковь расширена с обеих сторон каменной пристройкой. В 1820 гг. в ограде кладбища была построена двухэтажная каменная богадельня. 12 (24) сентября 1863 г. её посетил сын императора Александра II, цесаревич Николай Александрович (умерший в 1866 г.). В 1864 г. кладбище обнесено кирпичной стеной. С 1867 г. в Крестительской богадельне размещался приют для вдов и сирот духовного сословия.

В 1930 гг. церковь была закрыта. Действовала в 1942-44 гг. и опять была закрыта. Вновь открыта в 1960 гг. Как памятник архитектуры здание храма отмечено мемориальной доской. На территории Крестительского некрополя находятся могилы митрополита Орловском и Брянского Палладия (1896-1976), архиепископа Орловского и Брянского Варфоломея (1928-1988). Здесь похоронены краеведы Я. И. Горожанский (1858-1913) и П. И. Сизов (1931-1989), писатель и литературовед Л. Н. Афонин (1918-1975).

В южной части кладбища расположено братское захоронение советских воинов, погибших в боях за освобождение Орла в августе 1943 г. К 40-летию освобождения города в 1983 г. на нем сооружен мемориал. На металлических плитах обозначены имена павших бойцов и командиров. Здесь же 8 мая 1987 г. открыт восстановленный индивидуальный памятник командиру эскадрильи 61-й армии, майору Т. Г. Верховий, погибшему 3 мая 1943 г., первоначально похороненному в сквере Танкистов и перенесенному на Крестительское кладбище в 1952 г.