In 639, during his exile on the Rialto, St Magno, Bishop of Oderzo, had a vision of the Virgin, where she appeared as a very buxom and beautiful (formosa) matron and ordered him to build a church wherever a little white cloud settled.
It was the first Rialtine church dedicated to Mary, and was famously the parish church of the case-making guild or casselleri, who rescued the brides kidnapped by Dalmatian pirates; their reward was an annual visit by the Doge in the Feast of the Marys.
In 1492, Mauro Codussi rebuilt the church, maintaining its original Greek cross shape; the exterior is by unknown hands. The Austrians dropped an incendiary bomb through it in 1916 (you can see a bas-relief of the bomb just outside the right transept door), after which the dome was repaired.
Images by Miquel Rodríguez, Palma Vecchio, PD Art