Ömer'in hükümdarlığı sırasında Suriye valisi I. Muaviye, Akdeniz'deki adaları işgal etmek için bir deniz kuvveti kurulması yönünde talepte bulundu ancak Ömer, askerlerin risk altında olması nedeniyle bu öneriyi reddetti.Ancak Osman halife olduktan sonra Muaviye'nin isteğini onayladı.650 yılında Muaviye Kıbrıs'a saldırarak kısa bir kuşatmanın ardından başkent Constantia'yı fethetti, ancak yerel yöneticilerle bir anlaşma imzaladı.Bu sefer sırasındaMuhammed'in akrabası Ümmü Haram, Larnaka'daki Tuz Gölü yakınlarında katırından düşerek öldürüldü.Birçok yerel Müslüman ve Hıristiyan için kutsal mekan haline gelen aynı yere defnedildi ve 1816'da Osmanlılar tarafından Hala Sultan Tekkesi inşa edildi.Anlaşmanın ihlal edildiğini anlayan Araplar, 654 yılında beş yüz gemiyle adayı yeniden işgal ettiler.Ancak bu kez Kıbrıs'ta 12.000 kişilik bir garnizon bırakıldı ve ada Müslümanların etkisi altına girdi.Müslüman donanması Kıbrıs'tan ayrıldıktan sonra Girit'e, ardından da Rodos'a yöneldi ve fazla bir direnişle karşılaşmadan burayı fethetti.652'den 654'e kadar Müslümanlar Sicilya'ya karşı bir deniz seferi başlattılar ve adanın büyük bir bölümünü ele geçirdiler.Bundan kısa bir süre sonra Osman öldürüldü, yayılmacı politikasına son verildi ve Müslümanlar Sicilya'dan çekildi.655'te Bizans İmparatoru II. Constans, Phoinike'de (Likya açıklarında) Müslümanlara saldırmak için bir filoyu bizzat yönetti ancak filo yenilgiye uğradı: savaşta her iki taraf da ağır kayıplar verdi ve imparator ölümden kıl payı kurtuldu.