В течение VIII в. византийские императоры смогли удерживать власть над Сицилией. Произошло, правда, несколько локальных конфликтов из-за недовольства островитян иконоборческой политикой императоров Исаврийской династии. Но в то же время греческая составляющая на острове усилилась. Не предпринималось никаких попыток навязать иконоборчество на острове; многие иконопоклонники с востока нашли там убежище; к тому же императоры в свете их конфликта с Римской церковью, а также из соображений административного удобства перевели провинцию из подчинения Римской епархии, к которой Сицилия принадлежала прежде, в Константинопольскую. В IX в. мусульманские вторжения из Африки приняли серьезный оборот. Поводом было восстание одного из местных правителей, Евфимия, который провозгласил себя императором и призвал на помощь арабов. Захватчики высадились на острове в 827 г. Евфимий был вскоре убит, но арабы не ушли. В 831 г. они взяли Панорм, или Палермо, который переименовали в аль-Мадинах и сделали его своим опорным центром. Они продвигались медленно, если не считать западную часть острова, древнюю финикийскую территорию, где греческое влияние было самым слабым. Но в 842 г. они взяли Мессину, а в 857 или 858 г. — Кефаледий. Двумя годами позже захватчики укрепились в центральной части острова, взяв штурмом с помощью предателя почти неприступную крепость Генна, или Кастроджованни. Императоры сделали все возможное, чтобы спасти остров, но византийский флот, который пришел в упадок при Исаврийской династии, лишь недавно начал возрождаться. Византийцы сумели спасли Южную Италию, куда арабы тоже вторглись, но когда византийская столица Сицилии, Сиракузы, пала в 878 г., они ушли с острова. Таормина продержалась до 902 г., а несколько деревень на склонах Этны — чуть дольше, но к концу IX в. остров был под прочным арабским контролем.4
Арабы внесли оживление в сицилийский уклад. Они привезли лимон и апельсин, хлопок и сахарный тростник; правда, они быстро довершили начатое сицилийскими козами, расточительно вырубая леса. Арабы были прекрасными торговцами; в период их правления Палермо превратился в международный рынок, где купцам из христианских городов Италии были так же рады, как мусульманским купцам из Африки и с Востока. Многие поселенцы, арабы и африканцы, пришли вслед за своими армиями на остров, особенно на восточную его часть; но христиан это очень мало обеспокоило. И в самом деле, с финансовой точки зрения их жизнь стала, возможно, даже лучше, чем при византийском правлении, поскольку налоги были не слишком высокие, и крестьянам не приходилось оставлять свои поля ради службы в армии. Правда, шли многочисленные мелкие войны. Вначале арабские эмиры сохраняли верность африканским Аглабидам, но когда Аглабидов сменили неортодоксальные Фатимиды и Зириды, сицилийские правители провозгласили независимость и стали сражаться между собой и против африканцев, пытавшихся снова подчинить их. В начале XI в. византийцы попытались отвоевать остров и даже преуспели в этом на какое-то время, но им пришлось отвлечься на нормандцев, вторгшихся в византийскую Италию.5 В 1060 г. нормандцы решили завоевать Сицилию. Они уже захватили большую часть Южной Италии и поняли, что для того, чтобы создать сильное королевство, им необходимо также установить контроль над Сицилией. Но в то время как завоевания в Италии совершались группой баронов под предводительством Роберта Готвильского по прозвищу Гвискард и его союзников из числа лангобардской аристократии, завоеванием Сицилии занимались лишь Роберт Гвискард и его младший брат Рожер. Это оказалось долгим делом, поскольку у Готвилей было мало своих войск, и Гвискарду приходилось отвлекаться на проблемы на материке, а у Рожера, который и сделал большую часть работы, под началом часто оставалось не больше ста рыцарей. Но появление нормандцев приветствовалось христианским населением, а их успеху способствовал разлад в среде мусульман. Трое эмиров — эмиры Тра-пани, Палермо и Джирдженти, — поделившие между собой контроль на острове, завидовали друг другу. Союз с Ибн ад-Тимнахом, эмиром Палермо, позволил норманнам получить плацдарм на острове. Они захватили Мессину в 1061 г. Первая их попытка взять Палермо в 1064г., вскоре после смерти Ибн ад-Тимнаха, потерпела неудачу, но в 1068г. они разбили армию, посланную Зиридами из Африки для освобождения острова, после чего нормандцы стали медленно, но верно продвигаться дальше. После взятия Сиракуз в 1085 г. и Бутеры с Ното в 1088 и 1091 гг. завоевание острова было успешно завершено. Пока Роберт Гвискард был еще жив, он провозгласил совместное владение островом. Он заявил о своих правах сюзерена по отношению к брату, но Рожер удержал за собой титул графа Сицилийского и контроль над островом и над Калабрией. После смерти Гвискарда в 1085 г. его наследники были слишком слабы, чтобы отстаивать свои права, и граф Рожер стал править как независимый государь под верховным сюзеренитетом Папы Римского, который наделил нормандских правителей полномочиями завоевывать земли в Средиземноморье.