Secondo la tradizione, la nascita del santuario della Madonna di Barbana risale all'anno 582, quando una violenta mareggiata minacciò la città di Grado: l'eccezionale evento meteorologico, che allora destò grande stupore e preoccupazione, si inserisce probabilmente nella genesi dell'attuale laguna. Al termine della tempesta un'immagine della Madonna, trasportata dalle acque, venne ritrovata ai piedi di un olmo (o, secondo un'altra tradizione, sui suoi rami), nei pressi delle capanne di due eremiti originari del trevisano, Barbano e Tarilesso. Il luogo era allora relativamente lontano dalla linea di costa e il patriarca di Grado Elia (571-588), come ringraziamento alla Madonna per aver salvato la città dalla mareggiata, fece erigere una prima chiesa.

Attorno a Barbano si formò una prima comunità di monaci (i "barbaniti") che resse il santuario per i successivi quattro secoli. In questo arco di tempo il mare proseguì la sua avanzata: nel 734, da un documento di papa Gregorio III, si apprende infatti che Barbana fosse già un'isola. La chiesa venne probabilmente ricostruita più volte e la stessa immagine della Madonna, non si sa se una statua o un'icona, andò perduta.

Attorno all'anno mille, ai barbaniti subentrarono i benedettini che ufficiarono il santuario per cinquecento anni. A questo periodo risale la pestilenza che investì Grado nel 1237 e l'origine del pellegrinaggio annuale della città a Barbana.