Dopo la morte di Costante II e lo scontro tra i due imperatori, Mecezio e Costantino IV Pogonato, alla partenza di quest’ultimo, nel 669, a Siracusa sbarcarono gli Arabi. Depredarono le ricchezze accumulate nella città siciliana da Costante II grazie ai suoi saccheggi (tra i tanti, il bronzo del Pantheon). Pochi anni dopo ritentarono la sortita, ma stavolta furono sonoramente sconfitti, ed il pericolo arabo cessò per parecchio tempo.
La posizione della Sicilia, tuttavia, al centro del Mediterraneo, la faceva punto strategico per il controllo e la conquista dei paesi che vi si affacciavano. Per la diffusione del loro Credo, gli Arabi erano molto interessati a tale posizione strategica, e, a parte il tradimento di Eufemio da Messina, aspettavano solo il momento giusto per invaderla.
Agli inizi del IX secolo la politica alquanto debole di Costantinopoli, soprattutto per quanto riguardava le province occidentali, portò quest’ultime a governarsi in maniera quasi indipendente dal governo centrale. In coincidenza con il governo dell'Imperatrice Irene, anche il thema Sikelia, come quasi tutti gli altri, divenne sostanzialmente indipendente. Eufemio di Messina, turmarca della flotta siculo-bizantina, con l’aiuto di vari nobili siciliani, s’impadronì del governo in Sicilia, a scapito dei poteri locali. Senza chiedere aiuti esterni, i siciliani, che intendevano continuare a governarsi da soli, sconfissero e scacciarono Eufemio. Questi chiese aiuto, allora, agli Arabi, nell’828, per tornare padrone dell’isola. I Bizantini, al di là della forza amministrativa, non potevano stare a guardare e perdere la Sicilia, con la sua importanza strategica. Reagirono e inviarono un esercito al comando del generale Fotino, che sbaragliò il nemico a Siracusa, tanto che Eufemio, per mettersi in salvo, dovette fuggire in Africa (all'incirca nell'attuale Tunisia).
Eufemio trovò protezione presso la corte dell'emiro aghlabide di Qayrawān, Ziyādat Allāh I, a cui chiese un esercito per effettuare un nuovo sbarco in Sicilia. In quel periodo i musulmani erano interessati da contrasti intestini tra la componente berbera, originaria del luogo, e la componente araba proveniente dall’oriente. Forse proprio per risolvere le rivalità, l’emiro proclamò un jihad marittimo, raccogliendo volontari ovunque, e riuscendo ad organizzare una flotta di 70 navi.
Il 17 giugno dell' 827, i musulmani sbarcarono nei pressi di Capo Granitola, vicino Mazara del Vallo, conquistando, capitanati dal qādī di Qayrawān, Asad b. al-Furāt, quasi immediatamente, Marsala, il cui nome deriva proprio dall’arabo (Marsa ‘Alī, il porto di ‘Alī o Marsa Allāh, il porto di Dio). Sia Marsala che Mazara del Vallo furono dotate di mura e punti di difesa, soprattutto dei porti, concretizzando una vera e propria testa di ponte opportuna per la conquista della Sicilia. La cosa fu tutt’altro che facile e ci vollero decenni per completarla. Resistette Siracusa, dove alloggiava lo strategos bizantino da cui dipendevano il drungariato di Malta e i ducati di Calabria, Otranto e Napoli. La città fu espugnata il 21 maggio dell’878, e terminò col massacro di 5.000 abitanti. L’ultima città fortificata a cadere fu Tauromenium (Taormina) il 1º agosto del 902. L’ultima cittadina siciliana ad essere presa fu Rometta che si arrese solo nel 963.