The Muslim Aghlabids conquered Sicily between June 827 and 902, when the last major Byzantine stronghold on the island, Taormina, fell. Isolated fortresses remained in Byzantine hands until 965, but the island was henceforth under Arab Muslim rule until it was conquered in turn by the Normans in the late 11th century.

Although Sicily had been raided by the Muslim Arabs since the mid-7th century, these raids did not threaten Byzantine control over the island, which remained a largely peaceful backwater. The opportunity for the Aghlabid emirs of Ifriqiya (present-day Tunisia) came in 827, when the commander of the island's fleet, Euphemius, rose in revolt against the Byzantine Emperor Michael II. Defeated by loyalist forces and driven from the island, Euphemius sought the aid of the Aghlabids, an Arab dynasty. The latter regarded this as an opportunity for expansion and for diverting the energies of their own fractious military establishment and alleviating the criticism of the Islamic scholars by championing jihad, and dispatched an army to aid him. Following the Arab landing on the island, Euphemius was quickly sidelined. An initial assault on the island's capital, Syracuse, failed, but the Muslims were able to weather the subsequent Byzantine counter-attack and hold on to a few fortresses. With the aid of reinforcements from Ifriqiya and Umayyad al-Andalus, in 831 they took Palermo, which became the capital of the new Arab-Muslim province.

The Byzantine government sent a few expeditions to aid the locals against the Muslims, but preoccupied with the struggle against the Abbasids on their eastern frontier and with the Cretan Saracens in the Aegean Sea, it was unable to mount a sustained effort to drive back the Muslims, who over the next three decades raided Byzantine possessions almost unopposed. The strong fortress of Enna in the centre of the island was the main Byzantine bulwark against Muslim expansion, until its capture in 859. Following its fall, the Muslims increased their pressure against the eastern parts of the island, and, after a long siege, captured Syracuse in 878. The Byzantines retained control of some fortresses in the north-eastern corner of the island for some decades thereafter, and launched a number of efforts to recover the island until well into the 11th century, but were unable to seriously challenge Muslim control over Sicily. The fall of the last major Byzantine fortress, Taormina, in 902, is held to mark the completion of the Muslim conquest of Sicily.

Under Arab rule, Sicily prospered and eventually detached itself from Ifriqiya to form a semi-independent emirate. The island's Muslim community survived the Norman conquest in the late 11th century and even prospered under the Norman kings, giving birth to a unique cultural mix, until it was deported to Lucera in the 1220s after a failed uprising.

Throughout the imperial Roman period, Sicily was a quiet, prosperous backwater. Only in the 5th century did it suffer from raids by the Vandals operating from the coasts of Vandalic Africa. In 535, the island came under Byzantine control and was raided by the Ostrogoths in the Gothic War, but calm returned thereafter. Protected by the sea, the island was spared the ravages inflicted on Byzantine Italy through the Lombard invasions of the late 6th and early 7th centuries, and retained a still flourishing urban life and a civilian administration. It was only the increasing threat of the Muslim expansion that thrust it into the limelight. As John Bagnell Bury writes, "A fruitful land and a desirable possession in itself, Sicily's central position between the two basins of the Mediterranean rendered it an object of supreme importance to any Eastern sea-power which was commercially or politically aggressive; while for an ambitious ruler in Africa it was the steppingstone to Italy and the gates of the Adriatic."

Consequently, the island was early on targeted by the Muslims, the first raid occurring in 652, only a few years after the establishment of the first Muslim navy. Following the onset of Muslim attacks against North Africa, it became a crucial strategic base, and for a while, in 661–668, it was the residence of the imperial court under Constans II. Constituted as a theme around 690, its governing strategos also came to assume control over the scattered imperial possessions in the southern Italian mainland. The island was raided thereafter, especially in the first half of the 8th century, but did not come under serious threat until the Muslims completed their conquest of North Africa and moved into Hispania as well.

It was Abd al-Rahman al-Fihri, the Arab Abbasid governor of Ifriqiya, who first made plans to invade the island in force and attempt to capture it and Sardinia in 752–753, but he was thwarted by a Berber rebellion. In 799, the founder of the Aghlabid dynasty, Ibrahim ibn al-Aghlab, secured recognition of his position as autonomous emir of Ifriqiya by the Abbasid caliph, Harun al-Rashid, thereby marking the establishment of a practically independent state centred on modern Tunisia. In 805, Ibrahim concluded a ten-year truce with the Byzantine governor of Sicily, which was renewed by Ibrahim's son and successor Abdallah I in 813. During this time, the Aghlabids were too preoccupied with their rivalry with the Idrisids, Arab dynasty, to the west to plan any serious assault on Sicily. Instead, there are testimonies of commercial traffic between Sicily and Ifriqiya, and of the presence of Arab traders on the island.

The occasion for the invasion of Sicily was provided by the rebellion of the tourmarches Euphemius, commander of the island's fleet. According to later and possibly fictional accounts, driven by lust for a nun, he had forced her to marry him. Her brothers protested to Emperor Michael II, and the Byzantine ruler ordered the island's strategos, Constantine Soudas, to investigate the matter and if the charges were found true, to cut off Euphemius' nose as punishment. Thus it came that Euphemius, returning from a naval raid against the African coast, learned that he was to be arrested. Instead, he sailed for Syracuse, occupying the city, while the governor sought refuge in the interior. Euphemius soon managed to gain the support of a large part of the island's military leadership. Euphemius repulsed an attempt by Constantine to recover Syracuse, forcing the governor to flee to Catana. Euphemius' forces pursued and drove Constantine out of Catana, and eventually captured and executed him. Euphemius was then proclaimed emperor. The historian Alexander Vasiliev doubts the "romantic" story of the origin of Euphemius' revolt, and believes that the ambitious general simply used an opportune moment, when the central Byzantine government was weakened by the recent Revolt of Thomas the Slav, and by its preoccupation with the contemporary Muslim conquest of Crete, to seize power for himself.