Si, en el momento de la llegada de Alejo al poder, el estado general del Imperio era deplorable, la situación de la [[Armada bizantina|marina]] era desastrosa.232<ref>{{harvnb|Haldon|1999|p=91}}.</ref> Los años de guerra civil condujeron a un aumento de su decadencia, que comenzó a mediados del siglo XI. Por lo tanto, en el momento en que [[Roberto Guiscardo]] desembarcó en la costa albanesa, la armada bizantina no estaba en absoluto en estado para oponerse a él, lo que obligó al emperador a confiar en las flotas de las repúblicas italianas que le hicieron pagar caro por su ayuda.233<ref>{{harvnb|Birkenmeier|2002|p=39}}.</ref> Sin embargo, a lo largo de su reinado, trató de reafirmar el poder de la armada bizantina, esencial para la supervivencia del Imperio, ya que era probable que estuviera expuesta a amenazas marítimas, como el deseo de [[Tzacas]] de atacar Constantinopla.234<ref>{{harvnb|Ahrweiler|1966|p=185-186}}.</ref> Así, logró repeler la amenaza de este emir turco y recuperar gradualmente el control de la costa occidental del mar Egeo gracias a la acción de Juan Ducas. Del mismo modo, reafirmó la soberanía bizantina sobre Creta y Chipre. Paralelamente a esta refundación de una flota de guerra, se modificaron las estructuras de esta. Mientras que la antigua armada bizantina se dividió en flotas thematicas, ahora se agrupa en una flota unificada, dirigida por un ''[[Megaduque]]''. 235<ref>{{harvnb|Kazhdan|1991|p=1331}}.</ref> Este reemplaza al ''[[Drungario|Gran Drungario]]'', reducido al estado de segundo al mando. 236<ref>{{harvnb|Haldon|1999|p=96}}.</ref>
