A differenza di altre chiese veneziane, San Polo non è stata mai completamente ricostruita, sicché ha conservato l'impianto originale a tre navate tipico dell'architettura veneto-bizantina. I numerosi rimaneggiamenti, invece, ne fanno un edificio poco unitario dal punto di vista stilistico.

Subì una prima ristrutturazione tra il Tre e il Quattrocento e a questo periodo risalgono gli elementi gotici, in particolare il portale laterale archiacuto, con modanature a tortiglione e ornamenti floreali, le ogive della navata laterale e il rosone.

A partire dal 1804 sino alla riconsacrazione del 1838 la chiesa ha subito i pesanti interventi progettati da David Rossi: in quell'occasione furono sostituite le colonne della navata centrale, chiuse alcune aperture per aprirne altre e venne usato, nel complesso, un anomalo stile neoclassico. L'abside fu ricostruita a pianta semiottagonale con finestre centinate. I restauri conclusi di recente hanno in parte recuperato gli elementi quattrocenteschi, in particolare il soffitto a carena di nave, e rimossi gli inutili ornamenti ottocenteschi.

Sulla parete alla sinistra dell'ingresso principale si trova un'Ultima Cena di Jacopo Tintoretto mentre la pala del primo altare, Assunta e i santi, sarebbe da attribuire alla sua scuola. Le altre pareti recano dipinti di Paolo Piazza (San Silvestro battezza Costantino imperatore e Predicazione di San Paolo) e di Jacopo Guarana (Sacro Cuore di Gesù).

L'altare della cappella absidale di sinistra è arricchito dallo Sposalizio della Vergine di Paolo Veronese, mentre il presbiterio riporta varie tele di Palma il Giovane (tra le quali la Consegna delle chiavi a San Pietro, la Conversione di San Paolo e la Tentazione di Sant'Antonio abate) e due statue bronzee di Alessandro Vittoria (San Paolo e Sant'Antonio abate).

Nella navata centrale si trovano altri dipinti di un anonimo ottocentesco, raffiguranti i quattro evangelisti e vicende della vita di San Paolo. Sconosciuto sono anche gli autori del crocifisso dell'altare maggiore e dei dipinti della navata laterale destra (Presepio e Madonna col Bambino, quest'ultima attribuita a Pietro Zandomeneghi).

Il soffitto raffigura una Gloria degli angeli e una Resurrezione di Cristo di Giandomenico Tiepolo. Al padre Giambattista è invece attribuita la pala La Vergine appare a San Giovanni Nepomuceno, commissionata, sembra, dal re di Polonia Augusto III che aveva donato alla chiesa le reliquie del santo.