La chiesa di San Paolo fu edificata nel X secolo ed ebbe fin dalle origini la funzione di parrocchia, affidata dal 1295 all'Ordine della Beata Vergine del Monte Carmelo. I lavori furono affidati all'architetto Alberto Schiatti ed eseguiti secondo le norme vigenti della Controriforma. Alfonso II d'Este posò la prima pietra del nuovo tempio nel 1575 che fu riconsacrato nel 1611. Il monastero dei Carmelitani fu ampliato fino a tutto il XVII secolo fino ad occupare l'intero isolato. Fra il 1797 ed il 1798, con l'occupazione napoleonica, i monaci furono trasferiti presso la Certosa ed il monastero adibito a carcere fino al 1912.

L'interno a croce latina con cupola è diviso in tre navate ed è interamente decorato da affreschi. Ospita nelle navate laterali e nel transetto opere pittoriche e scultoree eseguite tra il XVI ed il XVII secolo. Le figure di "Santi Carmelitani" nella volta della navata centrale sono opera dello Scarsellino, (XVI secolo).

La navata sinistra ospita la Discesa dello Spirito Santo (XVII secolo) dello Scarsellino (terza cappella), la Resurrezione (quarta cappella), la Sacra Notte, la Circoncisione, lo Sposalizio di santa Caterina di Sebastiano Filippi detto il Bastianino (quinta cappella).

Il transetto destro presenta la pala di San Girolamo di Girolamo da Carpi. I Quattro Evangelisti nei pennacchi sono opera dello Scarsellino.

Nel presbiterio si trovano l'Adorazione dei Magi, la Conversione e la Decollazione di San Paolo di Domenico Mona (XVI secolo) e dello stesso autore la Gloria di San Paolo nella volta. L'affresco del catino absidale col Ratto di Elia (Elia rapito in cielo) è opera dello Scarsellino.

Nella navata di destra (terza cappella) vi sono la Natività del Battista, la Decapitazione del Battista, il Battesimo di Cristo dello Scarsellino e l'Annunciazione ed il San Paolo del Bastianino (quinta cappella).

La chiesa, oltre ad ospitare le tombe di Guarino Veronese, di Luzzasco Luzzaschi, di Alberto Lollio e di Giovan Francesco de Grossi (detto Siface), conserva anche opere di Carlo Bononi e Giacomo Parolini, nonché sculture di Francesco Casella, Andrea Ferreri e Filippo Porri.