Как свидетельствуют архивные документы, 7 августа 1858 г. жена надворного советника Мария Дмитриевна Руднева продала военному капеллану о. Бенитусу Липеню «в вечное и потомственное владение» пустопорожнее неудобное место с забором и обгорелыми материалами шириной 17 сажен и 1 аршин и длиной 15 сажен за 275 рублей. Участок находился в III части Орла, на территории православного прихода св. Павла Исповедника, на улицах Садовой и Введенской (ныне — улицы Горького и 7 ноября).
По поводу ходатайства католиков о разрешении на строительство каменного храма, поданного в ноябре следующего года, губернская строительно-дорожная компания ответила согласием. На эту цель среди прихожан было собрано 5028 рублей 91 копейка. Первоначально была сооружена временная деревянная часовня, а 21 сентября 1861 г. был утвержден проект строительства на ее месте каменного здания храма. В 1864 г. храм был завершен и в нем начались богослужения.
Храм представляет из себя вытянутый прямоугольник без выделения алтарной части. Стиль здания представляет из себя несколько наивную трактовку псевдоготики, характерную для третьей четверти XIX в. Фасад фланкируют две многогранных башенки, еще одна, увенчанная высоким шпилем, венчает конек крыши. Главный вход выделен глубокой нишей со стрельчатым завершением, над полукруглым порталом находится окно-розетта. Боковые стены его расчленены семью стрельчатыми окнами. В 1909 г. к тыльной стороне здания была пристроена ризница.
Внутри здание имело сводчатое перекрытие, стены расчленялись плоскими пилястрами. Основным акцентом интерьера являлся ажурный псевдоготический главный алтарь, представлявший собой пятичастную арку, в нишах которой были установлены статуи святых. Менса престола была украшена изображением Тайной Вечери. С обеих сторон алтаря находились две ниши, также в псевдоготическом обрамлении, в правой из них был вход в сакристию. Вдоль боковых стен пресвитерия были установлены еще два алтаря, являющихся уменьшенной копией главного. Слева, в оконной нише находилась кафедра для проповедей с богато украшенным балдахином. Над входом в храм были устроены хоры.
В 1925 г., в соответствии с новым законодательством, в местных органах власти был зарегистрирован римско-католический приход. Настоятелем его был о. Ян (Иван Осипович) Павлович. Согласно уставу общины, подписанному 12 мая 1925 г., церковное здание передавалось в бессрочное пользование приходу Непорочного Зачатия Пресвятой Девы Марии. Но уже в январе 1930 г. бесплатное пользование было отменено. Вместо этого была введена арендная плата, которую община аккуратно вносила до 1 января 1938 г.
В 1931 г. был арестован настоятель прихода о. Ян Павлович вместе с органисткой Софьей Станиславовной Романовской. Священник был приговорен к расстрелу, замененному затем 10 годами заключения в лагере. Вскоре был арестован и расстрелян о. Александр Кучинский, также служивший в храме. Всего из числа прихожан было репрессировано 74 человека, 6 из них — расстреляны.
Храм был закрыт 5 апреля 1938 г. на основании постановления оргкомитета ВЦИК по Орловской области и передан спортивному обществу «Динамо». В годы Великой Отечественной войны здание было незначительно повреждено (пострадала крыша, были разобраны полы и выбиты оконные рамы). В начале 1950 г. здание храма было передано заводу «Продмаш», руководство которого произвело капитальную перестройку его фасадов и интерьеров: помещение было разделено перекрытием на два этажа, были заложены высокие стрельчатые окна и пробиты новые, снесены шпили боковых башенок и уничтожена центральная башня, над входом появился балкон, устроенный вместо окна-розетты.
В 1990-х Орловская католическая община была вновь воссоздана. Решением Малого Совета Облсовета Орловской области от 06.07.1993 года № 81-7 здание бывшей католической церкви было принято на государственную охрану как памятник архитектуры местной категории. В 1998 постановлением Областной администрации здание бывшего католического костела передавалось римско–католическому приходу Непорочного зачатия Пресвятой Девы Марии в бессрочное безвозмездное пользование. Но вскоре это постановление отменили.
В 2002 году община приобрела участок за кинотеатром «Современник» по улице Кирпичной для получения разрешение на строительство нового храма. В 2004 были построены дом для священника, часовня и зал для занятий. Открытие приходского центра состоялось 29 августа, а 3 июля 2005 года центр освящён митрополитом Тадеушем Кондрусевичем во имя Непорочного зачатия Девы Марии.
