Перший католицький костел в Херсоні був побудований за ініціативою князя Григорія Потьомкіна. Він хотів зробити місто привабливим для іноземців. Так як більшість з них були католиками, приймається рішення побудувати саме римо-католицьку церкву.
Згідно з інформацією із державного архіву, наприкінці 1780-х років в Херсоні збудували дерев’яну церкву. Її автором був європеєць Елізум Шац. Кам’яний храм побудували у 1820-х роках. Через 20 років до нього прибудували вежу. В ті часи при церкві діяли школа та благодійна організація, що допомагала біднякам. Влітку 1849 року Херсон став центром єпархії, і костел освятили в Кафедральний собор.
Після жовтневої революції більшовики, на диво, дозволили прихожанам продовжити богослужіння. Однак вже в 1931 році ситуація докорінно змінюється – будівлю костелу забирають для господарських потреб. У повоєнні часи до основної споруди додали кілька прибудов, в яких розміщувалося майстерня з ремонту кіноапаратури. А з 1957 року тут працював кінотеатр, названий на честь павліка Морозова. Він функціонував навіть після проголошення незалежності України. Лише у 2000 році храм цілком передали парафіянам.