La costruzione di un primo Palazzo Ducale, di un palazzo, cioè, sede del doge non può non essere posteriore, sia pure soltanto di qualche anno (come è presumibile), al trasferimento da Malamocco a Venezia della sede del Governo, voluto da Agnello Partecipazio agli inizi del secolo IX per rendere la sede stessa più difendibile dai nemici che venivano dal mare.
Niente, però, è dato di sapere di questa prima costruzione, anche se si può presumere che sia stata eretta, vicino alla preesistente piccola chiesa di San Teodoro.
Nel 976 andò a fuoco in seguito alla sommossa contro Pietro Candiano IV e fu ricostruito così bene, da avere gli elogi di Ottone III. Nel 1105 la caduta di un fulmine causò notevoli danni all’edificio tanto che si dovette ricostruirlo suscitando questa volta l’ammirazione da parte di Enrico V che ne fu ospite nel 1116.
Nella seconda metà del secolo XII Sebastiano Ziani, eletto doge nel 1172, ne decise l’ampliamento e la costruzione prese la stessa planimetria di quello che vediamo oggi.
E’ pensabile che questa nuova costruzione sia stata più castello che palazzo; che avesse, cioè, torri e particolari sistemi di difesa. Nel 1177 vi fu ospite Federico Barbarossa in occasione della sua venuta a Venezia per la riconciliazione con Alessandro III.
