After the conquest of Syria, Egypt and North Africa, the Arabs turned their attention to the Mediterranean Sea, seeking to dominate the maritime trade routes at the expense of the Byzantines. Although they dared to lay siege to Constantinople in 674-678 and 716-717 respectively, they failed during this period to permanently hold any of the islands of the eastern and central Mediterranean. Even the conquest of the Iberian Peninsula, Sardinia and Corsica was carried out without strong naval support. However, by the 9th century the Arabs had acquired remarkable naval technology: they built their ships in the same way as the Byzantines, had learned to use liquid fire and had built ingenious machines for throwing flaming arrows. By developing naval technology and seamanship, they forced the Byzantines to accept the neutrality of Cyprus (8th century) and then managed to conquer Crete (823/828-961) and Sicily (826-902).

The importance of Crete for the Arabs was strategic from the beginning, due to its key position on the sea routes connecting Constantinople with North Africa, Sicily, and the Eastern Mediterranean. Raids on the island had begun as early as the 7th century. An invasion from the coast of Inatos (Tsoutsouros) had already been attempted in 716/7 AD, as documented by an Arabic inscription on a grave in the gorge of Mindris, but had been successfully repelled, as deduced from the Life of St. Andrew.

A century later the attempt was repeated, this time carefully planned and was successful. Abū Hafs Umar, at the head of a group of rebellious Andalusian Arabs, left the Iberian Peninsula in 714, arriving in Egypt in 718. With the help of the Egyptians, who provided armed ships and information to make them leave, they took advantage of the turmoil caused to the Byzantine fleet and the defence of the Aegean by the rebellion of Thomas Sklavos (821-823 AD). They managed to penetrate the well-fortified island from a weak defensive position. The long commercial exchanges of the Cretan ports with the centres of North Africa, which had long since passed into the hands of the Arabs, and the earlier raids had familiarised the latter with the Cretan coast. The invasion probably began in 823/4 AD, with the Arabs landing at Cape Haraki, now identified with Cape Listis, near Dermatos of Keratokampos. The invaders found the local population exhausted by hunger and the plague epidemics described in the Life of St Andrew but also discouraged and decimated by the consequences of the devastating earthquake of 795 AD, which turned most Cretan cities, including the capital Gortyn, into ruins. The conquest of Crete seems to have been gradual and was completed with the capture of Herakleion around 828 AD.