Ancora prima dell'arrivo dei romani nella zona (186 a.C.), l'attuale territorio di Eraclea era ricoperto dalle acque della laguna, da cui affioravano molti isolotti. Tra questi primeggiava per importanza e grandezza, l'isola di Melidissa, il cui toponimo rimane tuttora oscuro.
Alla successiva dominazione romana, seguirono orde barbariche che travolsero la terraferma veneta, evitando la laguna. Tra il 638 e il 640 d.C. i nobili di “Opitergium” (Oderzo), guidati dal vescovo San Magno , furono costretti da Rotari , re dei Longobardi, a lasciare la città e a trasferirsi nell'isola di Melidissa, cambiandone il nome in quello di “Heraclia ”, in onore dell’imperatore bizantino Eraclio.
Alla metà del VII sec. Eraclea era una città ricca e densamente popolata, tanto da far decidere che le redini del governo di tutte le isole fossero affidate ad un unico capo: il Doge. il primo seggio fu così assegnato nel 697 d.C. al Doge Paolo Lucio Anafesto, cittadino di Eraclea,