In de laatste maanden van 33 AH gaf ʿUthman ﵁ aan ʿAbdullah ibn Saʿd ibn Abi Sarh ﵁ de opdracht om een marine op te bouwen. De Byzantijnse vloot had de afgelopen jaren herhaalde aanvallen ondernomen op de Levantijnse kust, en de moslims hadden geen eigen zee-arm om te antwoorden. Muʿawiyah ﵁ had al onder ʿUmar ﵁ verzocht om een vloot te mogen bouwen; ʿUmar ﵁ had geweigerd, beducht voor de gevaren van de zee. ʿUthman ﵁ stemde toe, op voorwaarde dat geen man gedwongen werd te varen.
In de scheepswerven van Tyrus, Sidon en Alexandrië werden tweehonderd schepen gebouwd. Bekwame zeevarende stammen uit de kustgebieden — vooral uit Ghifar en Mazin — werden gerekruteerd. Hun bevelhebbers waren mannen die op zee thuis waren. De voorraden uit Egypte en de Levant werden naar de havens van Akaba en Alexandrië gestuurd, vanwaar de vloot zou uitvaren.
De aanstelling van ʿAbdullah ibn Saʿd ﵁ als opperbevelhebber wekte enige discussie. Hij was de eerder geapostaseerde halfbroer van ʿUthman ﵁ van de pleegmoederszijde, ooit door de Profeet ﷺ uit Mekka verbannen en later teruggekeerd. Maar ʿUthman ﵁ wist dat ʿAbdullah ﵁ een tactisch begaafd commandant was, en de keuze stond vast. In de winter van 33 AH werden de squadrons uit Syrië en Egypte naar Akaba gebracht voor de definitieve concentratie. Het Syrische squadron onder Muʿawiyah ﵁'s officieren zeilde langs de kust; het Egyptische squadron werd door ʿAmr ibn al-ʿAs ﵁'s mannen aangevoerd.
In Rajab 34 AH was de vloot vertrekkensgereed. Tweehonderd schepen, ongeveer twintigduizend gevechtsklare mannen, en proviand voor twee maanden lagen voor anker. ʿAbdullah ﵁ verzamelde zijn bevelhebbers en sprak hen toe over hun vijand: niet de Romeinen die zij van vroegere veldslagen kenden, maar een ander volk dat onder dezelfde keizerlijke vlag voer. De avondsalat werd op het dek verricht. Bij dageraad lichtten de ankers.