Di proprietà della Signoria, "l'isola dei cipressi", com'era denominata un tempo, vide sorgere nel X secolo un monastero benedettino che nel 1109, già arricchito di donazioni da papi e dogi, accolse le spoglie del protomartire Stefano, dando vita ad una tradizione, poi abbandonata, di trionfali processioni dogali nella notte di Natale.
Il complesso, ricostruito nel XIII secolo, fu ristrutturato e ampliato da Palladio che progettò e realizzò, in parte, il refettorio, i chiostri e la chiesa iniziata nel 1566 e conclusa dopo la sua morte.
La facciata, che si apre sul bacino di San Marco come contraltare alla Basilica, prevedeva una soluzione decisamente innovativa nel panorama veneziano, diversa rispetto all’attuale prospetto piano: un pronao sporgente con colonne giganti avrebbe dato alla chiesa le sembianze di un tempio classico.