After signing a peace treaty between Russia and Turkey (1774-1775) Russian territory extended to the Crimea and Alexander I invited German colonists to populate those desert lands of south "Novorosia". In this way in young Odessa and its suburbs appeared many Lutheran communities, and in 1803-1804 the city governor, the Duke de Richelieu, had to ask the Russian Emperor to send a pastor to Odessa. 8 years passed before the first pastor came to South Palmyra. The first Lutheran Church was built much later, in 1827. According to the plan of Charles Boffoue it would be built on the highest point of the city, where still stands the Church of St. Paul (Lutheran Church - Kirha).
At the end of 19th century many buildings were built around the church, in which educational, cultural and social works were led. Over time, however, all these buildings became dilapidated and were demolished. The new church, which could accommodate 1200 people, was built on this place over two years. When Soviet rule came, the Church of St. Paul was closed. At the time of occupation of Odessa by German-Romanian forces (1941-1942) the religious life of the Lutheran Church improved.In post-war years the religious use of the church was suppressed and it was used as a music hall. In 1976 there was a fire, which destroyed all the nave of the church.
In the second time the Evangelical Lutheran Church was recorded in Odessa in 1990 and practically right away started to petit for returning its church plot, the ruins of St. Paul's church and one of the neighbouring building, which had been built in the 19th century as an asylum for aged members of the community.With the assistance of the community of St. Paul, in 1993 the German Cultural Centre and "Bavarian House" were organized.
In 2002, at last reconstructed and completely rebuilt, the former asylum for the aged was revived as the "Church Centre of St. Paul". Restoration and construction works of the rest of the rooms are continuing.