The first church on the site was founded by Doge Giustiniano Participazio in the early 9th century to house the body of the saint to which it is dedicated, a gift of the Byzantine Emperor Leo V the Armenian, which it contains under the second altar on the right.

Antonio Gambello was the original architect, who started the building in the Gothic style, but the upper part of the facade with its arched windows and its columns, and the upper parts of the interior were completed by Mauro Codussi in early Renaissance style many years later.

The church was originally attached to a Benedictine monastery of nuns also founded by Participazio and various other doges of the family.

The nuns of this monastery mostly came from prominent noble families of the city and had a reputation for laxness in their observance of the monastic enclosure.

In 855, Pope Benedict III took refuge in the monastery while fleeing the violence of the Antipope Anastasius, whose election his supporters had challenged.