Secondo le fonti avrebbe origini molto antiche, alcuni ne collocano la nascita intorno al VI secolo per opera della famiglia Molino o Da Molin (come oratorio privato, però alcuni autori veneziani scrivono che fosse stata la famiglia Pisani a erigere la prima chiesa) mentre è maggiormente accreditata la costruzione intorno al 996 (ma nel 966 è già attestata una chiesa con lo stesso titolo) grazie all'iniziativa delle famiglie patrizie Barozzi, Aldicina e Equilia; esisteva sicuramente nel 1127, anno nel quale faceva testamento uno Stefano Fuscari de confinio Sancti Phantini. Si suppone che l'erezione a parrocchia sia da far risalire all'XI secolo, in un periodo in cui si ebbe una ridefinizione dell'amministrazione ecclesiastica in città.

Più volte distrutta da incendi, fu ricostruita nel XII secolo dai Pisani e ancora, a partire dal 25 marzo 1507, su progetto di Antonio Abbondi detto lo Scarpagnino, con l'aggiunta della cappella ad opera di Jacopo Tatti detto il Sansovino, che ne portò a termine la ricostruzione nel 1564.

All'interno, sull'altare maggiore, è presente una statua marmorea di circa cm 160, di Giuseppe Bernardi Torretti.