Ο Muawiya ήταν ένας από τους πρώτους που συνειδητοποίησε την πλήρη σημασία της ύπαρξης ναυτικού.Όσο ο βυζαντινός στόλος μπορούσε να πλεύσει στη Μεσόγειο αμαχητί, οι ακτές της Συρίας, της Παλαιστίνης καιτης Αιγύπτου δεν θα ήταν ποτέ ασφαλείς.Ο Muawiyah, μαζί με τον Abdullah ibn Sa'd, τον νέο κυβερνήτη της Αιγύπτου, έπεισαν με επιτυχία τον Uthman να τους δώσει την άδεια να ναυπηγήσουν έναν μεγάλο στόλο στα ναυπηγεία της Αιγύπτου και της Συρίας.Ο Mu'awiyah έπεισε τον χαλίφη ότι έπρεπε να δημιουργηθεί ένα νέο ναυτικό για να αντιμετωπίσει τη βυζαντινή ναυτική απειλή.Έτσι στρατολόγησε τον Ubadah ibn al-Samit, μαζί με μερικούς βετεράνους συντρόφους του Μωάμεθ, όπως ο Miqdad Ibn al-Aswad, ο Abu Dhar GhiFari, ο Shadaad ibn Aws, ο Khalid bin Zayd al-Ansari και ο Abu Ayyub al-Ansari, συμμετείχαν στην κατασκευή του το πρώτο μόνιμο μουσουλμανικό ναυτικό στη Μεσόγειο με επικεφαλής τον Muawiya.Αργότερα η Ubadah ενώθηκε με τον Abdallah ibn Qais για να κατασκευάσει την πρώτη παρτίδα των πλοίων στην Acre.