После подписания договора о мире между Россией и Турцией(1774-1775 гг).России отошел Крым и Александр І пригласил немецких колонистов заселить пустынные земли юга Новороссии. Так в молодой Одессе и ее окрестностях появились многочисленные лютеранские общины, и городской комендант Дюк де Ришелье в 1803-1804 годах вынужден был просить императора прислать в Одессу пастора. Но пройдет восемь лет, прежде чем в Южную Пальмиру прибудет первый пастор.
Первая же лютеранская церковь возникнет и того позже - в 1827 году. По плану архитектора Карла Боффо ее построят в самой высокой точке города, там, где и сейчас находится Церковь св. Павла (Кирха). В конце 19-го столетия вокруг церкви выросли многочисленные здания, в которых велась образовательная, культурная и социальная работа. Однако все эти постройки со временем обветшали и былиснесены. Новая церковь, вмещающая 1200 человек, была построена на этом месте через два года.Но с приходом советской власти Церковь св. Павла закрыли. Во время оккупации Одессы немецко-румынскими войсками (1941-1942 гг.) религиозная жизнь лютеранской церкви оживилась. В послевоенные годы храм был упразднен и перестроен в концертный зал. В 1976 году в нем случился пожар, уничтоживший весь неф церкви.
Во второй раз Евангелическо-лютеранская церковь зарегистрировалась в Одессе в 1990 году и практически сразу же начала хлопотать о возвращении ей церковного участка – руин Церкви св. Павла и соседнего здания, построенного в 19-м веке как приют для престарелых членов общины. При активном участии общины св. Павла в 1993 году был создан немецкий центр культуры и образования "Баварский дом". А в 2002 году наконец-то отреставрированный и полностью перестроенный бывший приют для престарелых возродился как Церковный центр св. Павла. Реставрационные и строительные работы остальных помещений продолжаются по сегодняшний день.
Расписание богослужений: воскресенье - 10.00