
În 823, un grup de exilați andaluzi a debarcat pe Creta și a început cucerirea acesteia. În mod tradițional, ei au fost descriși ca supraviețuitorii unei revolte eșuate împotriva emirului al-Hakam I al Cordobei în 818. De îndată ce împăratul Mihail al II-lea a aflat de debarcarea arabă și înainte ca andaluzii să-și fi asigurat controlul asupra întregii insule, el a reacționat și a trimis expediții succesive pentru a recupera insula. Pierderile suferite în timpul revoltei lui Toma Slavul au împiedicat însă capacitatea de răspuns a Bizanțului, iar dacă debarcarea a avut loc în 827/828, a intervenit și devierea navelor și a oamenilor pentru a contracara cucerirea treptată a Siciliei de către aghlabiții tunisieni.
Prima expediție, sub Photeinos, strategos al Temei Anatolice, și Damian, Contele Grajdului, a fost învinsă în luptă deschisă, unde Damian a fost ucis. Următoarea expediție a fost trimisă un an mai târziu și a cuprins 70 de nave sub strategos-ul Cibyrrhaeots Krateros. Inițial a fost victorios, dar bizantinii prea încrezători au fost apoi înfrânți într-un atac de noapte. Krateros a reușit să fugă în Kos, dar acolo a fost capturat de arabi și răstignit.