Подобно множеству других мест со старыми церквями, территория вокруг Санта Мария Формоза относится к самым ранним поселениям Венеции. Согласно легенде, в 639 г. епископу Одерцо св. Магнусу было видение Мадонны, которая явилась ему не в виде молодой девушки, а как красивая матрона (итал. — formosa). Мадонна попросила его соорудить церковь на том месте, где над островом зависло облако. В 1492 г. Мауро Кодусси получил заказ на строительство нового здания на месте обрушившейся церкви XI в.

Вероятно, сам архитектор ориентировался в своем проекте на здание предшествующей церкви, которое, в свою очередь, воспроизводило центральную часть церкви Сан Марко с ее куполами. Так возникла типично венецианская крестово-купольная церковь, в основе плана которой был квадрат, с тремя апсидами. Ясные формы, определяющие интерьер храма, вторят гладким, цилиндрическим апсидам снаружи.