The church was erected by the now-defunct religious order the "Humiliati" in the mid-14th century, under the direction of Tiberio da Parma, who is buried in the interior.

It was initially dedicated to St. Christopher, patron saint of those who travel by ferry,[1] but its popular name suggesting consecration to Holy Virgin comes from the following century, when an allegedly miraculous statue of the Madonna, commissioned for the Church of S. Maria Formosa but rejected, was brought to the Church from the nearby orchard (orto in Italian) where it had languished.

[1] The Humiliati were ousted in 1462 and the Madonna dell'Orto was assigned to the congregation of Canons Regular of San Giorgio in Alga.

Restoration was begun under Austrian rule in the 1840s and finished in 1869, by which time Venice had become part of the unified Kingdom of Italy.

Since 1931 the church is assigned to Saint Leonardo Murialdo's "Padri della congregazione di San Giuseppe".

[1] The Congregation operates a nearby guesthouse, the "Casa Vacanza Madonna dell'Orto Patronato Pio IX".

The portal is surmounted by a pointed arch with white stone decorations portraying, on the summit, St. Christopher, the Madonna and the Archangel Gabriel by Nicolò di Giovanni Fiorentino and Antonio Rizzo.

The first chapel on the right contains an altarpiece of St John Baptist with Saints Peter, Mark, Jerome, and Paul, by Cima da Conegliano.

The Presentation in the Temple is located over the entrance to the San Mauro chapel in the south aisle, close to the east end.

There are four funerary chapels built on the left side of the church, which house the remains of four of the most important Venetian patrician families.