I primi dogi di Venezia furono comandanti di un ducato bizantino della laguna, e per un secolo non abitarono a Rialto: la loro sede fu prima Cittanova, sulla terraferma, poi Malamocco. Il primo eletto in modo autonomo fu Orso, nel 726; Agnello Particiaco portò il potere a Rialto nell'811.
Venetia et Histria e il ducato della laguna
Nel V secolo il Nord Est d'Italia era l'ottava provincia dell'impero romano, la Venetia et Histria, che andava dall'Istria fino al fiume Adda. La spezzò l'invasione dei Longobardi, entrati in Italia nel 568 dalle Alpi Giulie: occuparono l'entroterra e lasciarono ai Bizantini una striscia di costa sull'Adriatico, che conservò il nome di Venezia. Il re Agilulfo prese Padova, Monselice e Mantova nei primi anni del VII secolo.
In laguna comandavano ufficiali bizantini: nella chiesa di Santa Maria di Torcello un'epigrafe del 639 ricorda che la fondò il magister militum Maurizio, per ordine dell'esarca Isacio, un armeno, ed è il comandante bizantino più antico che le fonti attestino con sicurezza in laguna. Quello stesso anno e nel 669, con due campagne, i re Rotari e Grimoaldo si impadronirono di Oderzo, il caposaldo bizantino di quanto rimaneva della provincia. Il comando militare dell'impero passò allora a Cittanova, presso l'attuale Eraclea, un centro nuovo costruito su basi più antiche: aveva una grande basilica, un vescovo e il comandante delle truppe imperiali, e controllava un territorio di piccoli villaggi rurali. Le cronache la chiamano anche Eraclea, in onore dell'imperatore bizantino Eraclio, e vi ripararono i profughi di Oderzo e di Altino.
Paulicio, il primo doge della tradizione
La tradizione mette all'inizio della serie dei dogi Paulicio Anafesto. La cronaca di Giovanni Diacono, scritta intorno all'anno Mille, racconta che i veneziani si riunirono in assemblea a Cittanova con il patriarca di Grado e i vescovi, decisero che era più onorevole obbedire a un duca che ai tribuni, ed elessero Paulicio, che poi firmò la pace con il re longobardo Liutprando e fissò i confini di Cittanova. La data, ricavata dagli anni dell'imperatore Anastasio II e di Liutprando, cade fra il 713 e il 715; la cronaca di Andrea Dandolo la porta invece al 697.
Giovanni Diacono, collaboratore del doge Pietro II Orseolo, aveva letto nell'archivio del Palazzo il Patto di Lotario dell'840, che parla dei confini di Cittanova e del pascolo delle greggi, ma non di un'elezione. Nel patto Paulicio compare accanto a Marcello, il magister militum delle Venezie: per questo c'è chi lo ritiene un duca longobardo, forse di Treviso, che trattò i confini con i veneziani. Dopo Paulicio la tradizione mette proprio Marcello, e poi Orso.
Orso, eletto nella rivolta del 726
La vera autonomia cominciò nel 726, quando l'imperatore Leone III abbracciò l'eresia iconoclasta e ordinò di distruggere le immagini sacre. Spinta da papa Gregorio II, tutta l'Italia bizantina insorse: in molti ducati gli ufficiali dell'esercito, ormai reclutati sul posto, scelsero duchi ostili all'imperatore. A Venezia fu eletto Orso, il primo duca scelto in modo autonomo in laguna, a cui Gregorio II scrisse una lettera; già nel 727, però, un privilegio concesso alla città di Grado indica la provincia di Venezia di nuovo sotto l'autorità imperiale. L'esarca Eutichio, che si era rifugiato in laguna dopo una prima conquista longobarda di Ravenna, forse nel 732 riebbe la capitale con l'aiuto di Orso.
Morì nel 737, ucciso durante una rivolta di aristocratici, e per cinque anni Venezia fu governata da altrettanti magistri militum, uno all'anno. Nel 742 il quinto fu deposto dalla popolazione, che diede il titolo di duca a Deusdedit, il figlio di Orso: lui trasferì subito la sede da Eraclea a Malamocco e nel 754 venne deposto e accecato.
Malamocco, Galbaio e i Franchi
Malamocco, che le cronache chiamano Metamauco, prende il nome dal Medoacus, l'antico nome del Brenta, e probabilmente non era il paese che porta questo nome al centro del Lido. Nella seconda metà dell'VIII secolo i Longobardi presero Ravenna, nel 751, e con la città cadde tutto l'esarcato bizantino; nel 774 Carlo Magno conquistò il regno longobardo, e Venezia dovette contare solo su sé stessa.
Dopo la caduta di Deusdedit si combatterono a lungo la fazione di Eraclea e quella di Malamocco, e molti duchi furono deposti e accecati. Maurizio Galbaio, forse eletto a Malamocco nel 764 e doge fino al 787, chiuse quel periodo di lotte fra le famiglie e introdusse la coreggenza, che associava al potere un successore e avviava una successione ereditaria. Nel 775 nacque il primo episcopato dell'area di Rialto, sull'isola di Olivolo, chiamata poi San Piero de Castelo, all'estrema periferia della città. Fra l'809 e l'810 la Venezia fu attaccata dai Franchi di re Pipino, figlio di Carlo Magno, che la tennero per poco tempo e dovettero ritirarsi quando la flotta bizantina tornò nell'Adriatico; con la pace di Aquisgrana dell'812 Venezia rimase nell'area d'influenza bizantina.
Agnello Particiaco e il Palazzo di Rialto
Dall'811 il nuovo duca Agnello Particiaco portò sull'isola di Rialto il cuore del potere politico e religioso, e in pochi anni la famiglia fondò il Palazzo Ducale, il monastero di San Zaccaria e poi la chiesa di San Marco. I Particiaci, che avevano terre e una piccola chiesa di famiglia sulla terraferma, nella zona del Brenta, governarono con Agnello e i figli Giovanni e Giustiniano, e spostarono per sempre il centro politico verso il Canal Grande, lasciando ai margini Olivolo, Torcello e Malamocco.
Con il Palazzo nacque una cancelleria: il primo documento d'archivio veneziano, dell'819, racconta che Agnello e Giustiniano, «per grazia di Dio» duchi della Venezia, si riunirono a Rialto col patriarca di Grado, il vescovo di Olivolo e tutti i veneziani per fondare il monastero ducale di Sant'Ilario, sulle terre di famiglia vicino al Brenta. Nell'828 le reliquie di san Marco, portate da Alessandria da mercanti veneziani, furono accolte nel Palazzo mentre si cominciava la chiesa, e nello stesso anno il testamento di Giustiniano Particiaco mostra il duca già impegnato nei commerci per mare.
Dopo l'812 l'indipendenza del ducato arrivò per gradi, senza strappi: il Patto di Lotario dell'840, che il duca Pietro Tradonico aveva chiesto all'imperatore, venne negoziato con il regno italico senza passare per Bisanzio e garantiva ai mercanti veneziani il libero transito nel regno; negli stessi anni a Venezia si batteva un denaro d'argento con la scritta Venetias e il nome del sovrano, l'imperatore Ludovico il Pio. Verso il 900 il duca Pietro Tribuno fece alzare un muro dall'isola di Olivolo fino al Canal Grande e tendere una catena all'imbocco del canale, sul modello di quella di Bisanzio sul Corno d'Oro.