This church, originally built in the 12th century has seen extensive modification including several changes to the height of the tower. In 1590, the tower reached its maximum height of almost 159 meters (522 feet) and it is said in some quarters that it was at that time the highest building in the world. The church has been fully destroyed by fire at least three times and the tower has been reconstructed even more frequently. The current height is 124 meters (407 feet).

Originally it was a Roman Catholic church dedicated to St. Olaf (also known as King Olaf the Second of Norway). During the Protestant Reformation, it became a Lutheran church and began to be one of two churches favored by the Baltic German elite of the city (the other being St Nicholas’s Church). 

By 1950, the Lutheran congregation had become too small for the church to be viable, as many Baltic Germans were forced out of Estonia by a pact between Hitler and Stalin before World War II. The church was then taken over by a Baptist congregation. The grip of the USSR over the structure was not loosened for many more years—from 1944 to 1991, the KGB used the church tower as a radio tower and an observation platform.

Today, that observation platform is open to the public and provides fantastic views across the city and the nearby port. However the body of the church itself, although in the relatively simple Baptist tradition is very attractive, particularly the original architectural forms and the magnificent pulpit. Several memorial plaques in German are a reminder of the days when the congregation of this church was mainly Baltic Germans.