Храм находится на восточной окраине города, рядом с железнодорожной линией Орел-Брянск, на территории Афанасьевского кладбища (основано по указу Правительствующего сената от 27 февраля 1887 г. как кладбище Введенского женского монастыря). Кладбище по указу Орловской духовной консистории стало именоваться Афанасьевским по названию погоста, на котором первоначально возник сам монастырь.

С первых лет существования кладбища на нем кроме умерших монахинь хоронили и жителей из близлежащих к монастырю местностей, но официально это было разрешено лишь в 1897 г. В том же году кладбище было обнесено кирпичной оградой. 23 июля (4 августа) 1895 г. на кладбище на средства благотворителей — генерал-лейтенанта М. Л. Духонина с супругой и купца Каверина в память об императоре Александре III освящена деревянная церковь Воскресения. Она предварительно была собрана в Москве и затем привезенная в Орел. Храм стоял на каменном фундаменте, бревенчатые стены были обшиты тесом. Во внешнем облике церкви проявилось увлечение узорчатыми формами XVII в. Храм завершался четырехгранным шатром с декоративными слухами. Радом с церковью в 1950-х годах была возведена звонница.

В 1960-1981 гг. настоятелем служил митрофорный протоиерей Петр Данилович Сарнацкий (Родился в 1914 г. в г. Вильно. Окончил Виленскую духовную семинарию и Теологический факультет Варшавского университета. Рукоположен во священика в 1937 г . С 1937 г. - священник, настоятель Св. Преображенской церкви п. Острино Гродненской области), который погребен слева от храма в первом ряду.

Воскресенская церковь на Афанасьевском кладбище до октября 1996 года являлась единственным сохранившимся деревянным культовым памятником архитектуры в области.

В октябре 1996 года в результате поджога церковь сгорела, на ее месте по проекту архитектора М. Б. Скоробогатова построен новый каменный храм, который освящен 30 сентября 2001 г. В 2010 году отремонтирован в знак светлой памяти рабы Божией Нины.