30 раджаба 216 года от Хиджры (12 (16) сентября 831) после годичной осады объединённые силы мусульман Сицилии, Испании и Африки овладели Палермо. Падение второго по значению города Сицилии стало возможным после того, как на помощь единоверцам прибыли корабли из Испании во главе с берберским флотоводцем Асбагом ибн Вакилем и из Ифрикии, посланные аглабидским правителем Зиядатуллахом I. Ожесточенная борьба за остров продолжалась еще более семидесяти лет, пока в 902 году под натиском мусульман не пал последний оплот ромеев — крепость Таормина. На Сицилии расцвела арабо-мусульманская цивилизация, а Палермо превратился в один из важнейших торговых портов Средиземноморья.
Первые годы правления византийского императора Михаила II Травла ознаменовались борьбой с мятежом Фомы Славянина, который объявил себя императором и двинулся к Константинополю. В борьбе против непопулярного и эгоистичного Михаила приняли участие и отдалённые провинции империи. Одной из них была Сицилия, где освободительное движение начал турмарх Евфимий. Судя по должности, он занимал второй военный чин в администрации фемы. Для установления контроля над островом в 826 г. на Сицилию прибыл стратиг Фотин, который получил от императора приказ наказать Евфимия, отрезав ему нос за то, что тот насильно взял в жены понравившуюся ему монахиню. Евфимий сумел нанести поражение Фотину и казнил его, но его власть была шаткой. Один из назначенных им наместников, называемый в арабских летописях Балатом (Палатом), а также находившийся с ним в родстве Михаил Палермский перешли на сторону византийского императора. Находясь в затруднительном положении, Евфимий вместе с верными ему отрядами отправился в североафриканский порт Сус, намереваясь предложить аглабидскому правителю Зиядатуллаху ибн Ибрахиму (817 — 838) верховную власть над островом на следующих условиях: Евфимий должен был править островом с титулом императора, но платить джизью аглабитскому эмиру, который, в свою очередь, должен был оказывать Евфимию военную поддержку.
Поскольку поддержка мятежного военачальника означала объявление войны Византийской империи, эмир Ифрикии вынес вопрос на обсуждение улемов Кайруана. Сдерживающим обстоятельством был мирный договор 813 года между аглабитским правителем Абу аль-Аббасом Абдуллахом ибн Ибрахимом и сицилийским патрицием Григорием, и богословам предстояло установить факт его нарушения сицилийцами. Среди условий 10-летнего соглашения был вопрос об обмене военнопленными и безопасности мусульманских купцов в Сицилии и византийских в Африке. Когда были получены свидетельства о том, что в сицилийских тюрьмах томились мусульманские пленники, кадий Кайруана Асад ибн аль-Фурат заявил, что договор утратил силу. До переезда в Ифрикию этот богослов учился в Медине у имама Малика, а в Ираке у двух учеников Абу Ханифы — Абу Йусуфа и Мухаммада аш-Шейбани, и поэтому он пользовался огромным авторитетом у Зиядатуллаха и остальных мусульман. В результате общее мнение склонилось к тому, чтобы начать военную экспедицию против Сицилии и поручить командование армией самому Асаду ибн аль-Фурату.
Когда мусульманская армия, состоявшая из 10 тысяч пехотинцев и 700 всадников, была готова к отплытию из порта Сус, Асад ибн аль-Фурат произвёл смотр войск и произнёс ободрительную речь. 14 июня 827 г. флотилия из 100 судов отправилась к берегам Сицилии и через три дня вошла в гавань Мадзара, где Евфимий рассчитывал встретиться со своими сторонниками. Сразу после высадки выявились противоречия между интересами мусульман и христиан. Несмотря на уверения Евфимия, Асад ибн аль-Фурат отказывался довериться ему полностью и не объединил силы мусульман и христиан. Из-за плохой координации войск первое столкновение на острове произошло по ошибке между отрядом мусульман и сторонниками Евфимия, которые, попав в плен, тотчас были отпущены. Когда же дело дошло до вооружённых столкновений с византийскими отрядами, Асад ибн аль-Фурат попросил христиан во время боев держаться в стороне, а во избежание новых казусов иметь какой-нибудь внешний отличительный знак. С тех пор ветка растения на голове отличала сторонников Евфимия от прочих византийцев.
Получив сведения о приближении отряда под командованием Балата, мусульмане выступили навстречу противнику и нанесли ему разгромное поражение. Судить о численности византийского гарнизона на острове трудно, поскольку сведения на этот счет в мусульманских и христианских источниках разнятся. Так или иначе, но после этой битвы мусульманская армия без всякого сопротивления пересекла остров и подступила к главному городу Сицилии — Сиракузам. Для того чтобы задержать продвижение мусульман до прихода подкрепления из Константинополя, жители Сиракуз отправили парламентёров и начали переговоры об условиях капитуляции. Одновременно они готовились к осаде, укрепляли городские стены и поспешно свозили в защищённые места церковные богатства и съестные припасы. В это же время Евфимий, ожидавший лучшего для себя развития событий, начал втайне подстрекать византийцев к сопротивлению. Когда намерения ромеев стали очевидными, кади Асад приказал осадить Сиракузы, отправив послание Зиядатуллаху с просьбой немедленно прислать подкрепление. Однако тот не мог прийти на помощь из-за нападения тосканских герцогов на североафриканское побережье.
Заняв каменоломни вокруг Сиракуз, Асад ибн аль-Фурат призвал флот блокировать порты, а сам сделал несколько вылазок и сжёг византийские корабли. Осада крепости затягивалась, и мусульмане стали испытывать острую нехватку продовольствия. В войске назревал бунт, и один из недовольных даже потребовал от командующего вернуться в Африку. Кади не растерялся и резко ответил: «Я не из тех, кто позволит мусульманам, выступившим в поход, вернуться домой, когда они ещё имеют столько надежд на победу!» Видя возрастающее недовольство войска, он даже пригрозил сжечь собственные корабли и своей решительностью сумел воодушевить остальных воинов. Тем временем на помощь осажденным подоспел отряд из Палермо. Мусульмане окопали себя широким рвом, перед которым изрыли почву многочисленными ямами, что было лучшей защитой против всадников. Ромеи, безусловно, были знакомы с такой тактикой, но атаковали мусульман и понесли большие потери. В результате положение Сиракуз стало критичным, а мусульмане больше не хотели слышать о перемирии.
Однако судьба уготовила муджахидам очередное испытание: осенью 828 года в арабском лагере разразилась эпидемия чумы, унесшая жизни многих воинов и кадия Асада ибн аль-Фурата. Новым командующим был избран Мухаммед ибн Абу аль-Джевари, перед которым стояла непростая задача. Ряды мусульман поредели, противник получил подкрепление, а выход из гавани был перекрыт венецианским флотом. Понимая, что прорваться через вражеские корабли не удастся, мусульмане приняли мужественное решение: они сожгли свои суда и углубились внутрь острова. Без припасов, неся на руках раненых, ифрикийцы совершили тяжёлый переход до Минео. После трехдневной осады город сдался, и в это же время прекратилась эпидемия чумы. Вдохновленные успехом мусульмане продолжили наступление: часть армии направилась к юго-западному побережью острова, овладев городом Агридженто, а другая часть двинулась дальше на северо-запад и достигла до Энны. Жители крепости, вступив в переговоры с мусульманами через Евфимия, вероломно убили его. Во время осады также погиб Мухаммед ибн Абу аль-Джевари, и его преемником был избран Зухейр ибн Гауса. Попытки взять город штурмом не принесли успеха, и вскоре подоспевшие силы византийцев нанесли мусульманам поражение и сняли осаду города.
В руках ифрикийцев оставались только Мадзара и Минео, отделённые друг от друга сотнями миль и враждебным населением. Мадзара ещё держалась, а защитники Минео, надломленные голодом, были готовы капитулировать. Но мужественные воины проявили терпение и дождались помощи от Всевышнего. Летом 830 года на Сицилию прибыл африканский флот из 300 кораблей, посланный эмиром Зиядатуллахом ибн Ибрахимом. Одновременно из Испании приплыл флот под командованием Асбага ибн Вакиля. Африканские арабы вступили в переговоры с маврами о совместных действиях против византийцев, и те согласились при условии, что командующим будет назначен Асбаг ибн Вакиль и ифрикийцы обеспечат его войско лошадьми. Эти условия были приняты, и объединённые силы мусульман приступили к военным действиям. Отряд мавров направился к Минео, который был осаждён византийским военачальником Феодотом, а ифрикийцы — к Палермо.
В августе 830 года Асбаг ибн Вакиль дал генеральное сражение силам патрикия Феодота. Под стенами города византийцы были разбиты, а сам Феодот пал в битве. Остатки византийского войска поспешили укрыться в Энне. На пути к этой крепости мавры осадили городок Кальтаниссетта, когда в их лагере разразилась эпидемия чумы. Смертельная болезнь сразила Асбага ибн Вакиля и нескольких других эмиров. Византийцы попытались воспользоваться замешательством в стане мусульман и перешли в наступление. В результате часть мавританского войска вернулась в Испанию, а часть примкнула к ифрикийской армии под Палермо.
Осада второго по значимости города Сицилии продолжалась целый год, с июля 830 до августа 831 года. Защитники крепости проявили героизм, сдерживая натиск мусульман, но не могли бороться с эпидемией моровой язвы. По словам Ибн аль-Асира, за время осады население крепости сократилось с 70 тысяч до трех тысяч человек! В конце концов спафарий Симеон согласился обсудить условия капитуляции и 12 сентября 831 года сдал город мусульманам, выторговав безопасность для себя и своей семьи, для местного епископа Луки и немногих знатных граждан. Все они благополучно отплыли в Константинополь. Остальное население постигла участь военнопленных.
Под властью мусульман Палермо приобрел большое торговое и военное значение. С разных уголков исламского мира сюда стекались воины, желавшие принять участие в новых походах, и сицилийские мусульмане начали организовывать набеги на итальянское побережье. С другой стороны, Сицилия превратилась в центр соприкосновения латинской, византийской и арабо-мусульманской культур. Неслучайно в Высокое Средневековье интерес к наукам и искусствам в Сицилии и Южной Италии был намного выше, чем во многих других областях Европы.