Христианство на территории Северо-Западного Причерноморья появилось уже спустя несколько десятилетий после смерти и воскресения Христова. Сюда в крымские каменоломни римские императоры ссылали христиан, считавшихся государственными преступниками. В их числе был третий наследник Апостола Петра, епископ Рима Климентий I. Папа Климентий помогал сосланным христианам и благовествовал Евангелие неверующим, приведя к спасению многих людей. Около 101 года он принял мученическую кончину ради Христа. Сегодня вновь созданная Одесско-Симферопольская епархия носит имя св. Климентия.

Несколько столетий спустя, в 654 году, после периода заточения и тяжких истязаний сюда был привезен Папа Мартин I. Он был сослан императором за то, что противостоял захлестнувшей в то время почти всю Церковь ереси монофизитизма. Папа умер от истощения, голода и нечеловеческого обращения 16 сентября 655 года. Его тело было похоронено в Херсонесе (неподалеку от Севастополя) в церкви Пресвятой Богородицы.

Однако более активная евангелизация этих земель и первые попытки создания церковных структур на землях современной Украины приходятся на конец первого тысячелетия. В своей римской форме христианство начало распространяться на Руси еще с IХ века сначала благодаря латинским епископам, которых назначали в разные города. Их не постоянное, а в основном временное, присутствие еще не означало существования епископств – организованной формы устройства Церкви. Их деятельность более напоминала миссии в новоокрещенной стране, чем действия епархиальных иерархов.

С ХІІІ века католицизм пропагандировали также францисканские и доминиканские монахи. При этом достаточно сильны были влияния венгров со стороны римско-католического архиепископства в Острихоме. С XIV века латинские епархии Руси-Украины входили в состав Львовской митрополии, которая была основана в 1375 году. Позднее, в 1783 году в Могилеве была создана новая митрополия, включившая в себя епархии Речи Посполитой, вошедшие в состав Российской империи после раздела Польши.

К 1333 году относится также попытка создания латинской епархии для южных земель современной Украины. Она была провозглашена буллой Папы Иоанна XXII «Quam gaudiosa sit Deo» 5 июля 1333 года, но вскоре пришла в упадок.
К идее создания епархии для южных земель Российской империи вернулся царский Комитет по церковным делам, разрабатывавший проект конкордата со Святейшим Престолом. Это привело к созданию в 1847 году Херсонской римско-католической епархии.

Идею установления епископства со столицей в Херсоне и резиденцией епископа-помощника в Саратове поддержал царь Николай І. Согласно с конкордатом и подтверждающей папской буллой достаточно большая территория новой епархии охватывала: Херсонскую, Екатеринославскую, Саратовскую, Крымскую, Астраханскую губернии, Кавказское генерал-губернаторство и Бессарабию. После Могилевского архиепископства это была крупнейшая епархия в России. Большой процент мирян составляли немецкие колонисты, прибывшие по приглашению Екатерины ІІ, а также поляки. Главными местами расселения католиков были Саратов и Одесса.

Первым епископом Херсонской епархии был назначен доминиканец Фердинанд Кан, а суфраганом (помощником) Викентий Липский. Местом пребывания епископа был определен Херсон. Но против этого выступил херсонский православный епископ, поэтому управление епархией было переведено в Тирасполь, в котором не было даже католического храма и других необходимых помещений.

Епархию переименовали в Тираспольскую. Из-за неподготовленности Тирасполя к размещению епархиальних служб управление перевели в Саратов, оставив название епархии – Тираспольская. Саратовский хрпм стал кафедральным собором. С созданием Тираспольской епархии в Одессе был создан деканат для наблюдения за приходскими церквями, большинство из которых находились в немецких колониях.

В 1856 году в Саратове открыли духовную семинарию, которая готовила священииков для поволжских южнороссийских немецких колоний. Эту семинарию закончили многие одесские священники.

Как самостоятельный деканат Тираспольской епархии Одесса, вместе с колониями, существовала с 1857 до 1926 года. Прелат Георгий Разутович, последний исполняющий обязанности надзирателя всех католических церквей Южной России, был первым деканом Одесского деканата – до 1876 года.
Вторым деканом стал почетный каноник Рудольф Рейхерт, который работал 22 года – с 1876 до 1898. Валентин Гартман руководил деканатом с 1898 до 1903 года. Последним деканом был пастор из колонии Мангейм, папский прелат Яков Добровольский.

В 1917 году Тираспольский епископ Иосиф Кесслер принял решение сделать Одессу местом пребывания епископа. Во времена советской власти католическое управление было реорганизовано, вместо двух деканатов – Одесского и Николаевского – были созданы три: Березанский, Одесский и Кучурганский (1926). К Одесскому деканату принадлежали приходы: Успения Пресвятой Богородицы, Святого Климентия, Святого Петра (Одесса), Мариєнталя, Йозефсталя, Францфельда Клейн-Либенталя, Клостендорфа, Херсона, Николаева, Зиновьевска, Васильевки. Деканом был священник храма Святого Климентия Иосиф Нейгум.

Приход Успения Пресвятой Богородицы, с филиалом Святого Петра насчитывал в 1920-х годах 14 986 прихожан, а храм был преобразован в кафедральный собор.