В 826 году Эвфемий, командующий византийским флотом на Сицилии, вынудил монахиню выйти за него замуж. Император Михаил II Травл приказал другому военачальнику, Константину, разорвать брак и отрезать Эвфемию нос. Эвфемий поднял восстание, убил Константина и занял Сиракузы. Затем он потерпел поражение и бежал в Северную Африку, где предложил свои услуги по завоеванию острова аглабидским эмирам, династии, формально подчинявшейся халифату, в обмен на безопасность и должность военачальника. Аглабиды послали на завоевание острова мусульманскую армию, которой командовал семидесятилетний кадий Асад ибн аль-Фурат. Армия включала около 10 тысяч пехотинцев, 700 всадников и размещалась на 100 кораблях. Была достигнута договорённость, что Эвфемий станет правителем Сицилии и будет платить ежегодную дань Аглабидам. После высадки войска в Мадзара-дель-Валло к нему присоединились верные Эвфемию войска. Первое сражение состоялось 15 июля 827 года около Мадзары и закончилось победой мусульманской армии. Затем Асад завоевал южное побережье острова и взял Сиракузы в осаду. После года осады, пережив мятеж, его войска смогли победить большое войско, посланное из Палермо и поддержанное венецианским флотом дожа Джустиниано Партечипацио. Затем, однако, мусульманская армия сильно пострадала от эпидемии чумы, от которой, в частности, умер Асад, и была вынуждена отойти в Минео. Перейдя в наступление, они попытались и не смогли взять крепость Кастроджованни, где погиб Эвфемий, и вернулись в Мадзару. В 830 году мусульмане получили подкрепление из 30 тысяч солдат из Африки и Андалусии. В июле и августе андалусские войска нанесли поражение византийской армии под командованием Теодота, но новая эпидемия чумы вынудила их отступить в Мадзару, а затем и отправиться обратно в Африку. Берберские же войска отправились на осаду Палермо и заняли город после годичной осады в 831 году. Палермо под названием Аль-Мадины стало мусульманской столицей Сицилии. Арабам потребовалось ещё более ста лет, чтобы полностью завоевать остров. В 902 была взята Таормина, и к 965 мусульмане контролировали всю Сицилию