The St Paul's congregation was formed as a separate congregation from St Mary's on 15 September 1910. The congregation continued to use St Mary's church until the new church was built. The land for the new church was received as a gift by the Tartu City Council in January 1911.

The church was designed by the famous Finnish architect Eliel Saarinen and was built in the Art Nouveau style. It is the only church in Estonia built in this style. Construction began in 1915 and the cornerstone was laid on 31 May; the church was consecrated on 1 October 1917. After two years of interior finishing, the church was again blessed on 9 November 1919 by Bishop Jakob Kukk. In 1919, the tower also had two steel church bells, which were made in Bochum. Germany. They weigh between 800 and 1,280 kg respectively. Central heating was installed in 1924 and cost a total of 700,000 marks.^[1][2]

On 17 March 1923 a new altar sculpture was inaugurated. The sculpture was the work of Amandus Adamson and was made out of Carrara marble and was 3.5 meters high. It was called "Come to me you who are weary and burdened" and depicted Jesus with Mary Magdalene on his right and Jericho on the left. It has cost a total of 1,400,000 Finnish markka.^[3]

The church burned on 25 August 1944 and most of the building was destroyed. The original plan of the congregation was to restore the church in its original form and dimensions. Work began in 1952, and in 1959 works on the roof vaulting began. The roof designs and the building supervision were done by the engineer Hugo Oengo [et]. Plastering and painting began in 1960.

In 1962 the Soviet authorities confiscated half of the church building to be used as a museum. The church was re-consecrated on 3 July 1966, and a month later the congregation had to vacate half the church to make room for the Estonian Sports Museum. The beams for the side balconies were removed in July 1966 because there was no need for side balconies. In the summer of 1967, another part of the church was taken over by the authorities to make way for the Ethnographic Museum (now the Estonian National Museum). Instead of the original 1,500 seating area, the church was by then only able to accommodate 350 seats.^[4]

In 2001, the Sports Museum relocated into a new premises and in September 2005, the Estonian National Museum also relocated and handed over to the congregation the part of the church which was used by the museum. Hence, by 2005, the interior of the building was once more combined and used as a church. Restoration commenced in 2005 and was completed by 2015 and was opened on 12 September 2015.^[5]

•  
  The tower
•  
  Interior
•  
  The pipe organ
•  
  The Amandus Adamson sculpture (1923)
•  
  Rebuilding the upper part of the tower
•  
  During restoration in 2010