La chiesa fu dedicata ai martiri romani Giovanni e Paolo vissuti nel III sec., costruita dai frati Domenicani tra il XIII ed il XV sec. e consacrata nell'anno 1430.
La facciata è composta di mattoni e suggerisce la divisione interna della chiesa a tre navate. Nella parte centrale è presente un grande occhio accompagnato da due aperture minori nelle parti laterali della facciata. Dalla foto si può apprezzare come la parte inferiore della facciata sia stata costruita in epoca più antica rispetto alla parte superiore e sia caratterizzata dalla presenza di archi gotici sprovvisti di apertura che racchiudono il portone d'entrata anch'esso gotico ma con chiari influssi rinascimentali. Tali archi sono luogo di sepoltura di dogi e personaggi in vista della Serenissima, ospitando ognuno un'urna funeraria (bianca nella foto). La discontinuità dei materiali tra il portale ed il resto della facciata si spiega con la realizzazione parziale di un progetto di rifacimento iniziato nel '400.
L'interno è a pianta a croce latina composta di tre navate e cappelle laterali, cinque colonne per lato dividono la navata principale dalle laterali.
La chiesa ospita molti monumenti funebri dei dogi di Venezia che qui venivano portati per l'onoranza funebre con corteo cittadino. Tra questi assume importanza assoluta il Monumento al Doge Pietro Mocenigo di Pietro Lombardo dove troneggia l'esaltazione delle virtù che il Doge seppe dimostrare in battaglia contro i turchi, così il Doge è raffigurato armato e l'urna è sostenuta da guerrieri.
Sulla navata di destra trova posto un polittico attribuito al Bellini dal Longhi nel 1914, dopo secoli di diatribe tra critici e studiosi. L'opera presenta La Pietà, La Vergine e l'Angelo Annunciante, Episodi della Vita di S. Vincenzo, Predica del Santo, Guarigione dei Paralitici.
Nella Cappella dell'Addolorata il Mausoleo della Famiglia Dogale dei Valier su disegno dell'architetto Andrea Tirali e realizzazione dei maestri scultori veneziani del '700.