Реальное завоевание началось в 825 году. Византийский адмирал Евфимий, которому в империи грозило наказание за некую провинность, характер которой не совсем понятен, восстал против императора и захватил остров. Позже, потерпев поражение от имперских сил, он бежал в Тунис со своими кораблями и обратился за помощью к Зиядет-Аллаху, правителю Туниса из династии Аглабидов, призывая его выступить и захватить остров. Несмотря на колебания, тунисский эмир отправил флот из 70–100 судов, который совершил высадку в Мазаре в 827 году. После быстрого первоначального наступления захватчиков ждало несколько неудач, и из трудного положения их спасло только неожиданное появление банды наемников из Испании. После этого наступление продолжилось. В 831 году мусульмане заняли Палермо, который стал и оставался столицей острова на протяжении всего периода мусульманского владычества и служил основой для дальнейшей экспансии. Морская и сухопутная война между византийскими и мусульманскими силами продолжалась на острове и в материковой Италии до 895–896 годов, когда византийцы подписали мир, по которому фактически отказались от Сицилии. Мусульмане захватили Мессину около 843 года, Кастроджованни – в 859, а Сиракузы – в 878 году. В то же время они высадились и на материке, и в течение какого-то времени их гарнизоны стояли в Бари и Таранто. Мусульманские набеги угрожали Неаполю, Риму и даже северу Италии и вынудили одного из римских пап выплачивать дань в течение двух лет. Между 882 и 915 годами мусульманское военное поселение у Гарильяно совершило набег в Кампанию и южную часть Лацио. Возможно, он был отправлен и поддержан с Сицилии.
Сицилия при мусульманском правлении сначала была подвластна Тунису и политически и административно привязана к этой провинции. С падением Аглабидов и приходом к власти Фатимидов новые халифы стали владеть островом. Сначала губернаторы острова назначались непосредственно верховным правительством или, в чрезвычайном положении, избирались палермской знатью. С переездом Фатимидов в Египет в 972 году контроль центрального правительства ослабел, и власть исподволь стала передаваться по наследству по линии Аль-Хасана ибн Али аль-Кальби. Это наследственное правление Кальбитов продолжалась до 1040 года и ознаменовало пик мощи и влияния мусульман на острове. Путешественник X века Ибн Хаукаль нашел в одном Палермо триста мечетей – красноречивое свидетельство проникновения ислама. Более поздние авторы говорят о ярком расцвете арабской культуры и литературы, от которой, к сожалению, мало что сохранилось.
Причиной падения Кальбитов стала гражданская война между сицилийскими и североафриканскими мусульманами, которая положила конец единству острова. После короткого интервала, в который городом Палермо правил совет знати, а остальным островом – местные князья, норманны, которые между тем оккупировали Южную Италию, вторглись и захватили большую часть острова. В 1061 году Рожер I взял Мессину и к 1091-му удерживал всю Сицилию, за исключением мелких застав, где еще держались мусульмане. Под властью норманнов, которая продолжалась до 1194 года, значительная часть культурного городского населения мигрировала в Северную Африку и Египет.
Арабы на Сицилии применяли в основном те же принципы управления, что и в завоеванных землях Востока, и существенным образом изменили систему владения и распределения земли. То, что на острове сохранилось множество арабских топонимов, показывает интенсивность колонизации, а многие арабские слова в сицилийском диалекте свидетельствуют об интересе арабов к сельскому хозяйству. Арабы принесли на Сицилию апельсины, шелковицу, сахарный тростник, пальмы и хлопок. Они расширили посевные площади за счет тщательного полива, и по сей день многие фонтаны Сицилии и особенно Палермо носят легкоузнаваемые арабские названия. До нашего времени сохранились некоторые памятники арабского владычества, но от книг, написанных арабами на Сицилии, за несколькими исключениями, сохранились только фрагменты, если сохранились вообще. Произведения крупнейшего арабского поэта острова Ибн Хамдиса (ум. 1132) дошли до нас только в испанском и сирийском переводах. Причины этого следует искать частично в использовании недолговечных материалов, частично в переселении, последовавшем за Нормандским завоеванием, но прежде всего в деструктивных действиях самих завоевателей.