Крестительское кладбище, на котором расположен храм, было образовано в 1772 году в юго-западной части Орла. Церковь во имя святого Иоанна Предтечи была заложена 2 июля 1774 года и освящена 20 июля 1777 года. Первоначально храм был холодным и имел только один престол во имя Предтечи и Крестителя Господня Иоанна. Сооружение велось в основном на средства жителей первой части города.
В 1823 году на кладбище была выстроена колокольня со шпилем. В 1827 году трапезная часть церкви была расширена, и освящены два новых престола — в честь Казанской иконы Божией Матери и иконы Божией Матери «Всех скорбящих Радость». С тех пор внешний облик храма сохраняется в почти неизменном виде.
В 20-е годы XIX века священником В. Переверзевым была сооружена двухэтажная каменная богадельня, встроенная в кладбищенскую ограду. В 1882–1887 годах её обратили во «временный приют», где содержалось 50 девочек духовного звания. 12 сентября 1883 года приют посетил цесаревич Николай Александрович. С 1887 года в Крестительской богадельне размещался приют для вдов и сирот духовного звания.
В 1938 году храм был закрыт. В 1942–1944 годах он был вновь открыт, а затем снова закрыт. В начале 1960-х годов храм был вновь открыт и передан верующим взамен закрытой Богоявленской церкви. Сюда были перевезены иконостас и богослужебная утварь из закрытой к тому времени Богоявленской церкви.
На Крестительском кладбище в 1812 году хоронили умерших от ран русских и французских солдат. Здесь находятся могилы митрополита Орловского и Брянского Палладия (1899–1977), архиепископа Орловского и Брянского Варфоломея (1928–1988). Недалеко от входа в церковь сохранилась могила архиепископа Н. П. Поликарпова (1887–1938) — отца известного авиаконструктора Н. П. Поликарпова. На Крестительском некрополе захоронены также многие известные орловцы: генерал-майор Д. П. Джунковский (1851–1923), участник русско-турецкой войны 1877–1878 годов, П. В. Сизов и Я. И. Горожанский — краеведы, писатель и литературовед Л. Н. Афонин (1918–1973) и другие.
В южной части кладбища расположено братское захоронение советских воинов, погибших в боях за освобождение Орла в августе 1943 года. 8 мая 1987 года здесь открыт памятник на могиле командира эскадрильи 1-й армии майора Т. Г. Верхомия, убитого в бою 3 мая 1943 года.
Главной святыней храма являются вериги святителя Тихона Задонского, возвращённые Церкви в 1988 году. В храме также находятся ковчег с мощами святых угодников Божиих, почитаемая Казанская икона Божией Матери и икона Матроны Московской.
