È ancora da chiarire l'origine della chiesa. Secondo Giuseppe Cappelletti sarebbe stata edificata da Obelario, primo vescovo di Olivolo, verso la fine dell'VIII secolo. Le cronache, invece, affermano che fu fondata nel 966 dalle famiglie Tron, Zusto e Adoaldo. Tuttavia, il cronista Andrea Dandolo, che descrisse il grave incendio del 1105, non la menziona e la prima testimonianza certa è un documento del 1127, dove è ricordata come parrocchia filiale di San Pietro. Nel 1331 è invece ricordata come collegiata. Secondo quanto riportano i resoconti delle visite pastorali del Settecento, San Stae era una parrocchia popolosa, ricca e vitale e i suoi parroci erano anche canonici della Basilica di San Marco. Con gli editti di Napoleone, divenne rettoria di San Cassiano, ma tornò parrocchiale nel 1953. Tuttavia, venne nuovamente soppressa nel 1965. Dall'anno successivo è una rettoriale indipendente. Al suo interno sono conservate alcune opere dei più celebri artisti veneziani barocchi di inizio settecento. Vi troviamo dipinti di Sebastiano Ricci, Giambattista Tiepolo, Giovanni Battista Pittoni e Giovanni Battista Piazzetta. La chiesa attuale fu riprogettata da Domenico Rossi. La costruzione della facciata gli fu affidata nel 1709; essa ha la forma di un tempio, con un imponente frontone triangolare, sostenuto da colonne che poggiano su alti piedistalli. Tipicamente barocca è la ghimberga a timpano spezzato sul portale d'ingresso.
Furono qui tumulati due dogi: Alvise II Mocenigo nel 1709, sotto la grande lapide al centro della chiesa; e Marco Foscarini nel 1763, nella cappella di famiglia.
L'interno, opera tardo secentesca con reminiscenze palladiane dell'architetto Giovanni Grassi, ha pianta ad unica navata e tre cappelle aperte su ciascun lato; al centro della chiesa una vasta pietra tombale segna il sepolcro della famiglia Mocenigo. Iniziando da destra, sui tre altari in successione si incontrano opere significative di Nicolò Bambini, Giuseppe Camerata e Antonio Balestra, quest'ultimo a decorare la cappella della confraternita dei "tiraoro e battioro" la cui scuola è adiacente la chiesa. Le tre cappelle a sinistra ospitano invece nell'ordine opere di Giuseppe Torretto e Pietro Baratta (Cappella Foscarini), di Francesco Migliori (L'Assunta, post 1722) e di Jacopo Amigoni (I Santi Caterina e Andrea, 1719). Il presbiterio ha la decorazione pittorica più significativa: sul soffitto troviamo una vasta tela di Bartolomeo Letterini (Le Virtù e due confratelli della Scuola del Santissimo, 1708), mentre alle pareti, sopra e sotto a due tele di Giuseppe Angeli (Sacrificio di Melchisedech e Caduta della manna, dopo il 1770), possiamo ammirare dodici tele di dimensioni minori che hanno per soggetto gli Apostoli e che furono realizzate grazie al lascito testamentario di Andrea Stazio (morto nel 1722).Tra queste spiccano capolavori assoluti quali il Martirio di San Bartolomeo (1722), opera giovanile di Giambattista Tiepolo, San Giacomo Maggiore (1717) di Giambattista Piazzetta e San Pietro liberato dal carcere (1717-24) di Sebastiano Ricci. Interessanti anche alcune opere conservate in sacrestia, tra le quali la Crocifissione di Maffeo Verona (sec. XVII), L'imperatore ordina di sacrificare agli idoli (1722) di Giambattista Pittoni e Sant'Eustachio in prigione di Bartolomeo Litterini (sec.XVIII).