[[Paolo Lucio Anafesto]] fu il primo doge della repubblica: la sua sede, della quale non rimangono resti, fu posta ad [[Eraclea]]: era ben diversa da quella attuale.<ref name=Z4>{{cita|Zanotto|p. 4}}.</ref><ref name=Z5>{{cita|Zanotto|p. 5}}.</ref> Causa continue lotte intestine e l'uccisione di [[Orso Ipato]], le funzioni dogali furono delegate per breve tempo a un magistrato eletto annualmente.<ref name=Z5/> Poiché [[Teodato Ipato]] accusava gli abitanti di Eraclea di aver ucciso suo padre, trasferì la propria sede nella fiorente cittadina di [[Malamocco]].<ref name=Z5/> La nuova casa dogale fu abbandonata nel [[812]] per ordine di [[Angelo Partecipazio]], che decise di trasferire la sede ducale a Rivoalto, luogo più sicuro,<ref name=Z8>{{cita|Zanotto|p. 8}}.</ref> edificandola su un terreno di sua proprietà.<ref name=brusegan123>{{cita|Brusegan|p. 123}}.</ref> L'edificio, completato sotto [[Pietro IV Candiano]], aveva l'aspetto di un castello:<ref>{{cita|Zanotto|p. 10}}.</ref><ref name=brusegan123/> si può affermare ciò con certezza perché riuscì a resistere a una rivolta popolare del [[976]]<ref>{{cita|Zanotto|p. 12}}.</ref> e dovevasi trattare di una struttura molto resistente.<ref>{{cita|Zanotto|p. 13}}.</ref>
Poiché [[Teodato Ipato]] accusava gli abitanti di Eraclea di aver ucciso suo padre, trasferì la propria sede nella fiorente cittadina di [[Malamocco]].<ref name=Z5/> La nuova casa dogale fu ben presto abbandonata, per ordine di [[Angelo Partecipazio]], che decise di trasferire la sede ducale a Rivoalto, luogo più sicuro.<ref name=Z8>{{cita|Zanotto|p. 8}}.</ref>
Tale trasferimento è databile all'anno [[812]]. Il nuovo palazzo, detto ''palatium ducis'', venne edificato attorno all'[[814]] nei pressi della chiesa dedicata a [[Teodoro di Amasea|San Teodoro]], poi sostituita dalla [[basilica di San Marco]] in seguito a un incendio,<ref name=Z8/> su un terreno di proprietà del doge.<ref name=brusegan123>{{cita|Brusegan|p. 123}}.</ref> Il cantiere venne concluso sotto il dogato di [[Pietro IV Candiano]]: di quella costruzione, eretta nella stessa area che ora è occupata da Palazzo Ducale, non rimane alcuna traccia, ma è probabile che l'edificio fosse stato realizzato (almeno parzialmente) in pietra e presentasse agli angoli quattro torrioni d'avvistamento e in mezzo una corte.<ref>{{cita|Zanotto|p. 10}}.</ref><ref name=brusegan123/> Il fatto che la casa del doge fosse estremamente fortificata è attestato in primo luogo dal fatto che riuscì a resistere alla rivolta scoppiata nel [[976]] contro [[Pietro IV Candiano|doge Pietro IV Candiano]]<ref>{{cita|Zanotto|p. 12}}.</ref> e in secondo luogo dal fatto che il doge [[Pietro I Orseolo]] riuscì a sostenere personalmente le spese per il rifacimento del palazzo dopo che questo era stato colpito da un incendio: ciò significa che i danni non erano stati eccessivi.<ref>{{cita|Zanotto|p. 13}}.</ref> L'edificio ricostruito era caratterizzato dalla presenza di un corpo centrale fortificato con torri angolari, circondato dall'acqua, le cui tracce ancora si intuiscono nell'assetto del piano loggiato.
