Tijdens het bewind van Umar stuurde de gouverneur van Syrië, Muawiyah I, een verzoek om een ​​zeemacht op te bouwen om de eilanden in de Middellandse Zee binnen te vallen, maar Umar verwierp het voorstel vanwege het risico voor de soldaten.Toen Uthman echter kalief werd, keurde hij het verzoek van Muawiyah goed.In 650 viel Muawiyah Cyprus aan en veroverde de hoofdstad Constantia, na een korte belegering, maar tekende een verdrag met de lokale heersers.Tijdens deze expeditie viel een familielid vanMohammed , Umm-Haram, van haar muilezel nabij het Zoutmeer bij Larnaca en werd gedood.Ze werd begraven op dezelfde plek, die een heilige plaats werd voor veel lokale moslims en christenen, en in 1816 werd daar de Hala Sultan Tekke gebouwd door de Ottomanen.Nadat ze een schending van het verdrag hadden vastgesteld, vielen de Arabieren het eiland in 654 opnieuw binnen met vijfhonderd schepen.Deze keer bleef er echter een garnizoen van 12.000 man achter op Cyprus, waardoor het eiland onder islamitische invloed kwam.Nadat ze Cyprus hadden verlaten, zette de moslimvloot koers naar Kreta en vervolgens naar Rhodos en veroverde ze zonder veel weerstand.Van 652 tot 654 lanceerden de moslims een zeecampagne tegen Sicilië en veroverden een groot deel van het eiland.Kort daarna werd Uthman vermoord, waarmee een einde kwam aan zijn expansionistische beleid, en de moslims trokken zich dienovereenkomstig terug uit Sicilië.In 655 leidde de Byzantijnse keizer Constans II persoonlijk een vloot om de moslims bij Phoinike (bij Lycië) aan te vallen, maar deze werd verslagen: beide partijen leden zware verliezen in de strijd en de keizer zelf vermeed ternauwernood de dood.