На городском плане 1828 года значился как Немецкая площадь квартал, где сейчас расположена кирха. 28 апреля 1824 года состоялось торжественное заложение фундамента первой лютеранской церкви святого Павла, и завершено было строительство в октябре 1827 года.
Автором этого сооружения стал архитектор Франц Боффо, спроектировавший Воронцовский дворец и Потемкинскую лестницу, для него это был первый большой проект. Располагалась церковь на самой высокой точке городского плато. А немцы в конце XIX века пришли к выводу, что кирха находится в плохом состоянии и требует большей прочности и вместимости, поэтому заказали данный проект архитектору Шеврембранду, одесскому немцу. В ней были ярко выраженные черты готического и романского стилей, и она была довольно таки больших размеров. Особой красотой декора и архитектурной композиции отличался северо-восточный фасад, который был решен в виде трехбашенной пирамиды. Из Марселя для кровли была завезена черепица трех типов, а общая сумма затраченных средств составила на тот момент 110 тысяч рублей.

Лютеранская церковь в 1897 году, вмещавшая в себе 1200 человек, была освящена. Однако ее превратили после Отечественной войны в спортзал, но спасибо Богу, что не взорвали. Шла борьба многие годы за то, чтобы не уничтожать этот памятник архитектуры.
Кирха является не только памятником архитектуры, но и памятником культуры города Одессы. Здесь играл на органе Теофил Рихтер, великолепный музыкант и отец гениального пианиста Святослава Рихтера. Именно в этой кирхе первые уроки музыки получил Светик (так в Одессе его называли) у своего отца в 20-30-е годы ХХ века. При кирхе располагалось приходское училище святого Павла, которое стало профтехучилищем в годы советской власти. Его закончил Валентин Глушко, гениальный ученый и отец советских ракетных двигателей. Он очень увлекался музыкой и восторженно слушал игру на органе Теофила Рихтера. Вел переписку с Циолковским, но пока еще не знал, какой путь выбрать — музыку или воздухоплавание. Его судьбу определил один случай, как рассказывал позже в интервью Валентин Петрович Глушко, у него в Ленинграде украли скрипку, поэтому «переквалифицироваться» пришлось в инженеры.