St Paul's church was built three times between 1577 and 1680. The current internal structure was completed by Francesco Sammut and Lorenzo Gafà in 1639. The façade was remodelled in the 19th century and consists of a wide central bay flanked by narrow bays all on two levels, with bell towers over the side bays. The central bay has a semi-circular arched main portal flanked by pairs of Ionic columns on high pedestals and fluted in the upper half. This arrangement is repeated at the upper storey with the dower columns in Composite order flanking a niche with a statue. A gable reminiscent of the medieval styles crowns this central bay. The side bays, including the towers, are comprised of three levels, with Ionic, Corinthian and Composite orders respectively. This highly ornamented façade uses somewhat a subtle eclectic mix of neo-classical with hints of Romanesque architecture, and reflects the architectural influences present at the end of the 19th century.

The sacristy of St Paul's Shipwreck church was built contemporaneous with the church in High Baroque architecture. The interior is sumptuously adorned and has a coffered ceiling.

The St Paul's Shipwreck oratory is to the left of the church's façade and consists of a single bay on two levels. The façade architecture is Neo Gothic with some applied Baroque around the portal.

Mepa scheduled the church of St Paul together with the oratory and sacristy as Grade 1 national monuments as per Government Notice number 276/08 in the Government Gazette dated March 28.