Während Umars Herrschaft sandte der Gouverneur von Syrien, Muawiyah I., einen Antrag auf den Aufbau einer Seestreitmacht, um die Inseln des Mittelmeers zu erobern, aber Umar lehnte den Vorschlag wegen der Gefahr für die Soldaten ab.Als Uthman jedoch Kalif wurde, stimmte er Muawiyahs Antrag zu.Im Jahr 650 griff Muawiya Zypern an und eroberte nach einer kurzen Belagerung die Hauptstadt Constantia, unterzeichnete jedoch einen Vertrag mit den örtlichen Herrschern.Während dieser Expedition fiel eine VerwandteMohammeds , Umm-Haram, in der Nähe des Salzsees bei Larnaca von ihrem Maultier und wurde getötet.Sie wurde an derselben Stelle begraben, die für viele einheimische Muslime und Christen zu einer heiligen Stätte wurde, und 1816 wurde dort von den Osmanen die Hala Sultan Tekke errichtet.Nachdem die Araber einen Vertragsbruch festgestellt hatten, fielen sie 654 mit fünfhundert Schiffen erneut auf der Insel ein.Diesmal blieb jedoch eine Garnison von 12.000 Mann auf Zypern zurück, was die Insel unter muslimischen Einfluss brachte.Nachdem sie Zypern verlassen hatte, machte sich die muslimische Flotte auf den Weg nach Kreta und dann nach Rhodos und eroberte sie ohne großen Widerstand.Von 652 bis 654 starteten die Muslime einen Seefeldzug gegen Sizilien und eroberten einen großen Teil der Insel.Bald darauf wurde Uthman ermordet, wodurch seine Expansionspolitik beendet wurde und die Muslime sich daraufhin aus Sizilien zurückzogen.Im Jahr 655 führte der byzantinische Kaiser Konstans II. persönlich eine Flotte an, um die Muslime bei Phoinike (vor Lykien) anzugreifen, doch die Flotte wurde besiegt: Beide Seiten erlitten in der Schlacht schwere Verluste, und der Kaiser selbst entging nur knapp dem Tod.