В 825 г. после утверждения своей власти Ал-Мамун послал в Египет своего полководца привести к повиновению египетского наместника, отложившегося от калифата, а равно отнять Александрию у испанских бунтовщиков. При таких условиях бежавшие из Кордовы арабы решились искать счастья в новой авантюре и избрали для этого остров Крит. Очень большая осведомленность арабов насчет беззащитного положения острова объясняется как прежними их походами и набегами на острова и прибрежные местности, так и точным знанием условий, в которых империя находилась именно в данное время. Под начальством избранного ими вождя Абу-Хафса и с согласия калифа испанские арабы пристали в 825 г. к Криту в бухте Суда и, не встречая почти никакого сопротивления, начали занимать критские города и производить набеги и опустошения в незащищенных местах. Чтобы отнять у арабов всякую мысль о возможности возвращения на родину, Абу-Хафс, по преданию, приказал уничтожить корабли и указал им строить укрепленный лагерь, который под именем Хандака и дал потом арабское наименование Кандии самому острову. Когда все укрепленные места перешли во власть арабов, местное население было обращено в рабство, и ислам стал насильственно вводиться между населением Крита. Со стороны империи предпринят был ряд мер к возвращению острова, но все меры оказались безуспешны, так что более 100 лет, именно до 961 г., Крит оставался под властью арабов. Стоит отметить, что в 826 г. явился на Крит стратиг анатолийской фемы протоспафарий Фотин и пытался возвратить остров под власть императора, но ему нанесено было сильное поражение, так что он едва мог спастись от плена. Другая попытка спасти Крит была сделана в 827 г. под начальством стратига Кратира.
?Хотя этому вождю и удалось одержать над арабами победу, но он вследствие беспечности и самоуверенности не только потерял все свое войско, но и сам попался в плен и был казнен арабами. С тех пор в течение 135 лет Византия не могла восстановить своей власти на этом острове.
Возвращаемся к истории сицилийских дел. Смелые искатели приключений, казалось, были оставлены здесь на произвол судьбы и ко времени вступления на престол царя Феофила (829) едва могли держаться в укреплении Мазара, первом опорном пункте, с которого и начались их завоевания в Сицилии. Но в 830 г. к арабам явилась помощь с двух сторон, так что скоро они сделались господами положения. С одной стороны, к Сицилии пристала испанская флотилия корсаров под начальством бербера Асбаг-ибн-Вакила по прозванию Фаргал, которая, впрочем, не имела цели оказать помощь стесненным единоверцам, руководясь исключительно желанием добычи. К тому же времени прибыл к Сицилии отряд судов, посланных Сиадет-Аллахом. Находившиеся в Сицилии арабы вошли с ними в переговоры насчет совместных действий против императорских гарнизонов в Сицилии, согласившись признать над собой высшую власть Асбаг-ибн-Вакила. Последний, имея· в своих руках значительные военные средства, начал ряд довольно успешных предприятий на острове. Прежде всего он пошел на крепость Минео, где стоял присланный императором стратиг Феодот.
В августе 830 г. арабы напали на греков и совершенно победили их, причем в битве пал и патрикий Феодот, а остатки греческого отряда заперлись в Кастроджованни. Но скоро затем разразившаяся в лагере победителей повальная болезнь, от которой погиб и сам начальник экспедиции, изменила взаимное отношение сторон. Греки снова стали стеснять арабов, и последние теряли постепенно занятые ими местности. В конце концов им не осталось другого исхода, как сесть на суда и возвратиться в Испанию. Из участников того отряда, который прибыл в Сицилию три года тому назад вместе с Асадом, осталась небольшая горсть воинов, которая заперлась теперь снова в Мазаре. Между тем, та часть африканских арабов, которая прибыла в Сицилию по поручению Сиадет-Аллаха, перенесла театр военных действий на север острова, пристав ко второму по значению городу Сицилии Палермо.
Осада Палермо продолжалась целый год, от июля 830 до августа 831 г. Густонаселенный город, в котором было не менее 70 000 жителей, сильно пострадал от неприятелей и от моровой язвы. Наконец, спафарий Симеон, бывший, вероятно, начальником гарнизона, вступил с арабами в переговоры об условиях сдачи города. Выговорив безопасность для себя и своей семьи, для епископа и немногих граждан, он принужден был сдать город на волю арабского предводителя и сам спасся в Константинополь. С тех пор положение арабов в Сицилии могло считаться вполне утвердившимся. Палермо составлял весьма важное приобретение и надежную точку опоры для дальнейших предприятий как на острове Сицилии, так и в Южной Италии. Независимо от этого, удобства культурного города, богатства, в нем найденные, и множество пленников — все это было хорошей наградой за испытанные прежде лишения и неудачи. Приобретенные арабами в Сицилии успехи и мировое значение Палермской гавани стали привлекать сюда массу новых искателей приключений со всех концов мусульманского мира.