In the final months of 33 AH, ʿUthman ﵁ ordered ʿAbdullah ibn Saʿd ibn Abi Sarh ﵁ to build a navy. The Byzantine fleet had launched repeated attacks on the Levantine coast in recent years, and the Muslims had no naval arm of their own with which to answer. Muʿawiyah ﵁ had already asked permission under ʿUmar ﵁ to build a fleet; ʿUmar ﵁ had refused, wary of the dangers of the sea. ʿUthman ﵁ consented, on the condition that no man be forced to sail.
In the shipyards of Tyre, Sidon and Alexandria, two hundred ships were built. Skilled seafaring tribes from the coastal regions — above all from Ghifar and Mazin — were recruited. Their commanders were men at home on the sea. Supplies from Egypt and the Levant were sent to the ports of Akaba and Alexandria, from which the fleet would sail.
The appointment of ʿAbdullah ibn Saʿd ﵁ as supreme commander stirred some debate. He was the formerly apostatized half-brother of ʿUthman ﵁ on the foster-mother’s side, once banished from Mecca by the Prophet ﷺ and later returned. But ʿUthman ﵁ knew that ʿAbdullah ﵁ was a tactically gifted commander, and the choice stood. In the winter of 33 AH the squadrons from Syria and Egypt were brought to Akaba for the final concentration. The Syrian squadron sailed along the coast under Muʿawiyah ﵁'s officers; the Egyptian squadron was led by ʿAmr ibn al-ʿAs ﵁'s men.
By Rajab 34 AH the fleet was ready to depart. Two hundred ships, some twenty thousand battle-ready men, and provisions for two months lay at anchor. ʿAbdullah ﵁ gathered his commanders and spoke to them about their enemy: not the Romans they knew from earlier battles, but a different people sailing under the same imperial flag. The evening salat was performed on deck. At daybreak the anchors were weighed.