Selon les données d'archives, le 7 août 1858, Maria Dmitrievna Rudneva, épouse d'un conseiller, a vendu un terrain à Orel au père Benitus Lipen, aumônier militaire. Ce terrain, situé sur le territoire de la paroisse orthodoxe de saint Paul le Confesseur, à l'intersection des rues Sadovaya et Vvedenskaya (aujourd'hui rues Gorky et 7 novembre), a été vendu pour 275 roubles.

En novembre de l'année suivante, les catholiques ont soumis une demande de permis de construire une église en pierre, et la société de construction routière de la province a donné son accord. Parmi les paroissiens, 5028 roubles et 91 kopecks ont été collectés. Une chapelle en bois temporaire a d'abord été construite, et le 21 septembre 1861, le projet de l'église en pierre a été approuvé à sa place. En 1864, la construction a été achevée et les services religieux ont commencé.

L'église était un rectangle allongé sans partie altar distincte, réalisée dans le style néogothique, caractéristique du troisième quart du XIXe siècle. La façade était ornée de deux petites tours polygonales, et une troisième tour avec un haut clocher surmontait le toit. L'entrée principale se distinguait par une niche profonde avec une finition en arc brisé, au-dessus du portail semi-circulaire se trouvait une fenêtre en rosace. Les murs latéraux étaient divisés par sept fenêtres en arc brisé. En 1909, une sacristie a été ajoutée à l'arrière du bâtiment.

L'espace intérieur de l'église avait un plafond voûté, et les murs étaient décorés de pilastres plats. L'élément principal de l'intérieur était un autel principal en néogothique ajouré avec un arc en cinq parties et des statues de saints dans des niches. La mensa de l'autel était ornée d'une représentation de la Cène. De chaque côté de l'autel se trouvaient des niches, dont l'une menait à la sacristie. Le long des murs latéraux du presbytère se trouvaient deux autels supplémentaires, des copies réduites de l'autel principal. À gauche se trouvait une chaire pour les sermons avec un baldaquin richement décoré. Au-dessus de l'entrée de l'église, des chœurs étaient aménagés.

En 1925, conformément à la nouvelle législation, la paroisse romaine catholique a été enregistrée auprès des autorités locales. Le père Jan Pavlovich est devenu le recteur. Le bâtiment de l'église a été transféré à l'usage indéfini de la paroisse de l'Immaculée Conception de la Sainte Vierge Marie, mais en janvier 1930, l'usage gratuit a été annulé et un loyer a été introduit, que la communauté a payé jusqu'au 1er janvier 1938.

En 1931, le recteur Jan Pavlovich et l'organiste Sofia Romanovska ont été arrêtés. Le prêtre a été condamné à mort, peine commuée en 10 ans de prison. Peu après, le père Alexander Kuchinsky a également été arrêté et fusillé. Au total, 74 paroissiens ont été réprimés, dont 6 fusillés.

Le 5 avril 1938, l'église a été fermée par décision du comité d'organisation du VTsIK pour la région d'Orel et transférée à la société sportive "Dynamo". Pendant la Grande Guerre patriotique, le bâtiment a subi peu de dommages. Au début des années 1950, il a été transféré à l'usine "Prodmash", qui a complètement reconstruit les façades et les intérieurs : le bâtiment a été divisé en deux étages, des fenêtres hautes ont été murées, les flèches des petites tours et la tour centrale ont été démolies, et un balcon a été aménagé au-dessus de l'entrée.

Dans les années 1990, la communauté catholique à Orel a été restaurée. En 1993, le bâtiment de l'ancienne église catholique a été placé sous protection de l'État en tant que monument architectural. En 1998, le bâtiment a été transféré à la paroisse romaine catholique, mais cette décision a été annulée peu après.

En 2002, la communauté a acquis un terrain rue Kirpichnaya pour construire une nouvelle église. En 2004, une maison pour le prêtre, une chapelle et une salle pour les cours ont été construites. Le centre paroissial a ouvert le 29 août, et le 3 juillet 2005, il a été consacré par l'archevêque Tadeusz Kondrusiewicz au nom de l'Immaculée Conception de la Vierge Marie.