Ukoronowanie ich starań miało miejsce w 698 roku, kiedy to wojska kalifatu zdobyły Kartaginę, jedną z największych i najważniejszych baz floty bizantyjskiej. Zwycięstwo to otworzyło im drogę do opanowania zachodniej części Morza Śródziemnego. Przejęcie kontroli nad tym akwenem przez muzułmanów miało daleko idące skutki dla mieszkańców Italii.
Gubernator północnej Afryki, Musa ibn Nusajr, zaraz po zdobyciu Kartaginy, rozpoczął budowę infrastruktury koniecznej do stworzenia floty. Jego bazą był Tunis, gdzie rozbudowano port i stworzono stocznię. Po zakończeniu tych prac rozkazał skonstruowanie stu statków. Mieszkańcy wybrzeży i wysp włoskich bardzo szybko odczuli skutki tego projektu. Flota północnoafrykańska bardzo często atakowała, łupiła, a nawet podbijała właśnie te tereny. W 700 roku Arabowie opanowali Pantellerię. W 704 roku złupili zachodnią Sycylię. Rok później najechali Syrakuzy. W 711 roku Arabowie po raz pierwszy najechali Sardynię, a w 713 Korsykę. Obydwie wyspy zostały w krótkim czasie podbite i znalazły się pod władzą arabską. W 720 roku ponownie złupiona została Sycylia, a od 727 do 734 roku najazdy na tę wyspę odbywały się corocznie. W 728 roku zawarto wprawdzie rozejm, ale już rok później flota około 180 statków ponownie złupiła Syrakuzy.