The convent and the church dates to the origins of Venice in the early Middle Ages.
The monastery and the church, according to a legend, was founded by the
Zancaruol family. The site stood at a strategic point for the nascent Venetian power: at the main access to the sea.
From here, in 996 and 998, sailed off the first Venetian expeditions against the Narentine pirates. On 9 May 1000, the fleet led by Doge Pietro Orseolo II took off for the campaign that led to the submission of Dalmatia. This event is still remembered in the Marriage of the Sea ceremony. In this church, Doge Domenico Selvo was elected and crowned in 1071, since St Mark's Basilica was under reconstruction. In 1099, the Venetian participation in the First Crusade departed from this port, led by the Bishop of Olivolo and Giovanni, son of the doge
Vitale Michiel I.
In 1100, the relics of the body of St. Nicholas were putatively stolen from Myra of Lycia, and interred in this church. However, a few years earlier, in 1089, the remains of the saint had been entombed in Bari by Pope Urban II in person.
Nicholas was proclaimed protector of the Venetian fleet. In 1202, the forces of the Fourth Crusade left from here. In 1245
Salinguerra II of Torelli was buried here; he was a Ghibelline nobleman who held the city of Ferrara for many years, and who disputed the primacy of Este family. In 1623 the relics of St. Nicholas were transferred from the church to the monastery to accommodate the construction of the new building, before being placed back below the altar.