In 823, a group of Andalusian exiles landed on Crete and began its conquest. Traditionally they have been described as the survivors of a failed revolt against the emir al-Hakam I of Córdoba in 818. As soon as Emperor Michael II learned of the Arab landing, and before the Andalusians had secured their control over the entire island, he reacted and sent successive expeditions to recover the island. Losses suffered during the revolt of Thomas the Slav hampered Byzantium's ability to respond, however, and if the landing occurred in 827/828, the diversion of ships and men to counter the gradual conquest of Sicily by the Tunisian Aghlabids also interfered.

The first expedition, under Photeinos, strategos of the Anatolic Theme, and Damian, Count of the Stable, was defeated in open battle, where Damian was killed. The next expedition was sent a year later and comprised 70 ships under the strategos of the Cibyrrhaeots Krateros. It was initially victorious, but the overconfident Byzantines were then routed in a night attack. Krateros managed to flee to Kos, but there he was captured by the Arabs and crucified.