Furono richiesti rinforzi, che arrivarono in parte dall'Ifrīqiya, e in maggior parte da al-Andalus, oltre ad un gruppo di mercenari al comando del berbero Asbagh b. Wakīl, detto Farghalūs.
Con l’arrivo di nuove truppe, le sorti della guerra girarono a favore dei musulmani, che vinsero e uccisero Teodoto (nell’830), e conquistarono Palermo (nell’831). Fu poi la volta di Messina, Modica e Ragusa, mentre Castrogiovanni (oggi Enna) fu conquistata solo nell'859. La presa dell’intera Sicilia fu lenta ma inesorabile. La resistenza degli abitanti del solo Val di Mazara durò fino all’841, l'859 per la Val di Noto e la Val Demone. Siracusa, oltrepassato il blocco impostale tra l'872 e l'873 da Khafāja b. Sufyān b. Sawādan, cadde in mano mussulmana il 21 maggio 878. Tra le ultime roccaforti ad arrendersi vi fu Tauromenium (Taormina) il 1º agosto del 902 a causa dell’assedio dell'emiro Abū l-Abbās Ibrāhīm b. Ahmad.
Sotto il comando di diversi capitani, vittoriosi, ma a volte uccisi e sostituiti, la guerra durò per anni, fino alla conquista di Rometta (in provincia di Messina) nel 965, ultimo baluardo bizantino a cadere. Il capoluogo dell’isola, scelto dai musulmani, divenne Palermo (Siqilliyya).
La dominazione fu tutt’altro che tranquilla. I bizantini non smisero mai di ritentare di riprendersi l’isola. Diverse furono le spedizioni: quella di Niceta nel 963, di Niceforo nel 989 e quella di Giorgio Maniace. Quest’ultimo per ben quattro anni, dal 1038 al 1042, mantenne il possesso di Siracusa e della parte orientale della Sicilia. Per rinforzare le difese della città, fece costruire il castello che ancora oggi porta il suo nome. Faceva parte del suo esercito un gruppo di mercenari normanni, prima avanguardia di quelli che, tra poco, riguadagnato il possesso cristiano della Sicilia,  avrebbero aperto uno dei più importanti periodi storici siciliani e del meridione italiano.