L'église fut construite par la congrégation des Humiliés vers le milieu du XIVe siècle sur un projet de Fra Tiberio de Parme, dont la sépulture se trouve dans l'église. Elle fut d'abord dédiée à Saint Christophe, le saint patron des voyageurs. C'est au XVe siècle qu'elle fut consacrée à la Vierge quand, dans un verger voisin, on trouva une statue de la Madonne présumée miraculeuse, d'où le nom de Madonna dell’Orto. L'église reposait sur de faibles fondations et pour cette raison le Grand Conseil affecta le 11 novembre 1399 deux cents ducats à une importante œuvre de réfection conduite la même année.
Par décret du Conseil des Dix, approuvé par le Pape, les Humiliés furent chassés en raison de leur mœurs dépravés. L'église fut alors assignée aux Chanoines séculiers de Saint Georges, supprimée en 1668.
Le couvent de la Madonna dell'Orto passa en 1669 aux Cisterciens de Lombardie. En 1787, les Cisterciens cessèrent également leur activité en ces lieux et l'église fut transférée à l'administration publique avec à sa tête un recteur et quelques prêtres. En 1810, elle fut déclarée oratoire de Saint Martial et, en 1841, le gouvernement autrichien ordonna une retauration générale à ses frais. La restauration de la façade intervint en 1845, tandis que les travaux pour le reste de l'édifice débutèrent en 1855 mais ils n'allèrent pas à leur terme. L'église fut alors cédée aux militaires qui en firent un dépôt de paille. 1864 vit la reprise des travaux de restauration, terminés en 1869.
La façade et le cloître datent de 1460-1464, avec des statues du début du XVIe siècle. Le campanile et la coupole datent de la même époque. L'intérieur est enrichi de tableaux de Jacopo Robusti, dit Le Tintoret, enterré dans la nef de droite. le contrat de commande de ces tableaux, daté du 14 mai 1565, est encore conservé,