The present building was constructed in the Gothic style between 1513 and 1525 on the remains of earlier Roman and Romanesque churches, making it the latest surviving Gothic church in the city. It is one of the churches maintained and supported by the Förderverein Romanische Kirchen Köln. The surviving Romanesque west tower dates to 1170. It and the nearby Cäcilienkirche are the city's only two surviving double-churches, which combined a parish church with a collegiate church or Stiftkirche. In the nightbombing raid on 29 June 1943, known as the "Peter-und-Paul-Angriffs", the church's parish was almost completely destroyed, with the church building itself leveled to its foundations and its pillars destroyed. Efforts were made to secure the more important pieces of church furniture such as the stained glass and altarpieces, but much of the opulent woodwork such as the altars, pulpits and 1907 organ in its 1820 case were lost to the fire. Initial measures were put in place to make the site safe in 1950 and the rest of the restoration was almost complete by 1960, led by government architects Karl Band and Wilhelm Schorn. With few resources and a prevailing consensus to emphasize what had been lost, Band's restoration was "sensitive, but ultimately only as a fragment", producing an almost Protestant effect compared to its pre-war appearance. A redbrick nave contrasted with a raised bluestone chancel, while a new dark wood coffered ceiling was added – the city conservator Hiltrud Kier remarked that the ceiling's effect "was similar to a coffin lid". She also stated that the new vaulted ceilings between the clerestory windows were "like architectural tears" reminiscent of the lost vaulting. Only a few restored or reconstructed furnishings were placed in the building, including the medieval font and the wrought iron Baroque grille. In July 1960 the Jesuits took over the church and in September of that year one of them, Alois Schuh, was made the parish priest. A new, simple stone high-altar was later added and in 1961 the altarpieces by Cornelius Schut and Rubens returned to the church; and the surviving stained glass windows were reinstalled. The building was restored again between 1997 and 2000 to designs by Wiegmann & Trübenbach.
