Secondo la tradizione, la chiesa dedicata a San Paolo (Polo in veneziano) venne fondata nel IX secolo. Nel corso del XV secolo, all'impianto originario vennero aggiunti gli elementi gotici visibili sul fianco laterale: le monofore e il portale attribuito a Bartolomeo Bon. Nel 1804 un pesante restauro di Davide Rossi sovrappose una decorazione neoclassica in parte eliminata dal recente intervento che ha portato alla luce il soffitto a carena di nave analogo a quelli di Santo Stefano e di San Giacomo dell'Orio.