Muawiya az elsők között volt, aki felismerte a haditengerészet teljes fontosságát;Amíg a bizánci flotta ellenállás nélkül hajózhat a Földközi-tengeren, Szíria, Palesztina ésEgyiptom partjai soha nem lesznek biztonságban.Muawiyah Abdullah ibn Sa'ddal, Egyiptom új kormányzójával együtt sikeresen meggyőzte Uthmant, hogy adjanak engedélyt nekik egy nagy flotta építésére Egyiptom és Szíria hajógyáraiban.Mu'awiyah meggyőzte a kalifát, hogy új haditengerészetet kell létrehozni, hogy szembenézzenek a bizánci tengeri fenyegetéssel.Ezért beszervezte Ubadah ibn al-Számit, valamint Mohamed néhány veterán társát, mint például Miqdad Ibn al-Aswad, Abu Dhar GhiFari, Shadaad ibn Aws, Khalid bin Zayd al-Ansari és Abu Ayyub al-Ansari, akik részt vettek a the építésében. Az első muszlim állandó haditengerészet a Földközi-tengeren, amelyet Muawiya vezetett.Később Ubadah is csatlakozott Abdallah ibn Qaishoz, hogy megépítse az első hajót Acre-ben.