Kościół św. Klemensa znajduje się w samym centrum ponad 400-tysięcznego miasta. Jego budowę ukończono w 1911 r., gdy tamtejsza wspólnota katolicka liczyła 3 tys. wiernych. Zamknięta w czasie prześladowań religijnych świątynia, została uszkodzona w czasie bombardowań w latach II wojny światowej. W 1958 r. została przekształcona w kino, które funkcjonowało do 2006 r. Od tej pory budynek był zamknięty.

Wspólnota katolicka w Sewastopolu odrodziła się w 1993 r. Trzy lata później zaczęto odprawiać Msze w budynku sąsiadującym z kinem.

Rezydujący na Krymie biskup pomocniczy diecezji odesko-symferopolskiej Jacek Pyl powiedział, że „zwrot kościoła św. Klemensa wspólnocie katolickiej jest nadzwyczajnym wydarzeniem”. - Trudno znaleźć słowa, by wyrazić naszą radość. Historia jest pełna ran, a jedną z nich jest zamknięty i sprofanowany kościół - zaznaczył hierarcha.