The church that G. E. Street (1824-1881), one of England's foremost architects of the late 19th century, designed for St. Paul's reflects his interest in northern Italian brick-and-marble work, and owes much in its inspiration to the medieval church of San Zeno in Verona. In plan, St. Paul's is a longitudinal church with nave, clerestory, and side aisles of seven bays, with an elevated choir and apsidal chancel. The side aisles are vaulted with limestone ribs and brick webs or severies, and the nave spanned by broad trusses with simulated segmental barrel vaults of wood. The transverse masonry arches that span the nave at the entrance to the choir and chancel were used as fields for two of the mosaics by Edward Burne-Jones. On the south the first bay of the side aisle, under the campanile or belltower, houses the baptistry; the seventh or last bay is walled in to provide a sacristy.

The interior and exterior masonry is composed of what Dr. Nevin called "lake-colored" brick from Siena, alternating in uneven courses with travertine from Tivoli. The facade is simple in outline but bold in detail with the campanile placed aasymmetrically to the south.