Muawiya was one of the first to realize the full importance of having a navy; as long as the Byzantine fleet could sail the Mediterranean unopposed, the coastlines of Syria, Palestine and Egypt would never be safe. Muawiyah, along with Abdullah ibn Sa'd, the new governor of Egypt, successfully persuaded Uthman to give them permission to construct a large fleet in the dockyards of Egypt and Syria. Mu'awiyah convinced the caliph a new navy had to be established in order to confront Byzantine naval threat. So he recruited Ubadah ibn al-Samit, along with some veteran companions of Muhammad such as Miqdad Ibn al-Aswad, Abu Dhar GhiFari, Shadaad ibn Aws, Khalid bin Zayd al-Ansari, and Abu Ayyub al-Ansari, participated in building the first Muslim standing Navy in Mediterrania which led by Muawiya. Later Ubadah also joined Abdallah ibn Qais to built the first batch of the ships in Acre.