Euphemius was a Byzantine admiral, probably born in Messina. Around 826, according to Michele Amari, the Byzantine Emperor appointed a new governor of Sicily called either Constantine or Photinus, who in turn entrusted a naval command to Euphemius, a landowner with a large following. Accused on a perhaps trumped-up charge of abducting a young nun from a convent, he organized an uprising against the Byzantine Emperor, Michael II, and, after some military successes, proclaimed himself emperor in Syracuse, independent from Constantinople. In practice, he was a charismatic chief, and, respected as a king, the title of emperor meant that he dominated the whole territory of the island. Realising that he would be defeated by Byzantine troops when reinforcements were sent from the East, he appealed to Muslim leaders of Ifriqiya, where he asked the help of Arabs to take Sicily and Malta from the Byzantines. In the high summer of 827 he joined his forces with a large fleet commanded by Asad ibn al-Furat, but died later that year, killed by members of the imperial garrison at Castrogiovanni (Enna). He is considered to be the man who initiated the Arab invasion of Sicily and Malta and the beginning of the two-century Islamic domination on the island as the Emirate of Sicily.
In 826 Euphemius, the commander of the Byzantine fleet of Sicily, forced a nun to marry him. Emperor Michael II caught wind of the matter and ordered that General Constantine end the marriage and cut off Euphemius' nose. Euphemius rose up, killed Constantine and then occupied Syracuse; he in turn was defeated and driven out to North Africa. He offered rule of Sicily over to Ziyadat Allah the Aghlabid Emir of Tunisia in return for a place as a general and safety; an Arab army was sent. The latter agreed to conquer Sicily, promising to give it to Euphemius in exchange for a yearly tribute, and entrusted its conquest to the 70-year-old qadi Asad ibn al-Furat. The Muslim force counted 10,000 infantry, 700 cavalry and 100 ships, reinforced by Euphemius' ships and, after the landing at Mazara del Vallo. A first battle against the loyal Byzantine troops occurred on July 15, 827, near Mazara, resulting in an Aghlabid victory. Asad subsequently conquered the southern shore of the island and laid siege to Syracuse. After a year of siege, and an attempted mutiny, his troops were however able to defeat a large army sent from Palermo, also backed by a Venetian fleet led by Doge Giustiniano Participazio. But when a plague killed many of the Muslim troops, as well as Asad himself, the Muslims retreated to the castle of Mineo. Later they returned to the offensive, but failed to conquer Castrogiovanni (Enna, where Euphemius died) and retreated back to Mazara. In 830 they received a strong reinforcement of 30,000 Ifriqiyan and Andalusian troops. The Iberian Muslims defeated the Byzantine commander Teodotus in July–August of that year, but again a plague forced them to return to Mazara and then to Ifriqiya. The Ifriqiyan units sent to besiege Palermo managed to capture it after a year long siege in September 831. Palermo became the Muslim capital of Sicily, renamed al-Madinah ("The City"). The conquest was a see-saw affair; with considerable resistance and many internal struggles, it took over a century for Byzantine Sicily to be conquered.
The western third of Sicily fell relatively quickly into Muslim hands, but conquest of the eastern portion of the island was a protracted and haphazard affair. There is little evidence of large-scale campaigns or pitched battles, and warfare was dominated by repeated Arab attacks on Byzantine citadels, coupled with raids in the surrounding countryside, aimed at looting or the extraction of tribute and prisoners from the threatened localities. In this type of warfare, the south-eastern third of the island (Val di Noto) suffered comparatively more than the more mountainous and inaccessible north-eastern portion. No operations are reported in Sicily for the first two years after the fall of Palermo. The Muslims were probably preoccupied with organizing their new province, while the Byzantines were too weak to react, and could not expect any reinforcements: the Empire faced mounting pressure in the East, where the
Abbasid Caliph al-Ma'mun launched repeated invasions of the Byzantine borderlands and threatened to march on Constantinople itself until his sudden death in August 833. The struggle during the next few years focused on Enna, which became the main Byzantine stronghold in central Sicily. In early 834, Abu Fihr campaigned against Enna, defeated its garrison in the field and forced it to withdraw within the town's fortifications. In spring, the garrison sallied forth, but was again defeated and driven back. In 835, Abu Fihr again raided central Sicily, and defeated the army under a Byzantine patrikios (probably the island's strategos) that opposed him, taking the Byzantine commander's wife and son captive in the process. After his success, Abu Fihr sent Muhammad ibn Salim in a raid against the eastern parts of the island, which reached as far as Taormina . However, dissensions broke out once again among the Muslims: Abu Fihr was murdered, and his killers found refuge among the Byzantines. The Aghlabids replaced Abu Fihr with al-Fadl ibn Yaqub, who displayed great energy: immediately after his arrival he led a raid against the environs of Syracuse, and then another into central Sicily, around Enna. The Byzantine strategos marched out to meet them, but the Muslims withdrew to a mountainous and thickly forested area where the Byzantines could not pursue. After waiting in vain for the Muslims to accept battle, the strategos turned his army back, but was ambushed by the Muslims who put his men to flight. The Muslims seized most of the Byzantines' arms, equipment and animals, and almost managed to capture the severely wounded strategos himself. Despite his success, Ibn Yaqub was replaced in September by a new governor, the Aghlabid prince Abu'l-Aghlab Ibrahim ibn Abdallah ibn al-Aghlab , a first cousin of the emir Ziyadat Allah. At the same time, the long-awaited Byzantine reinforcements arrived. The Byzantine fleet contested the passage of Abu'l-Aghlab's small fleet, which lost ships both to the Byzantine attack and to storms; the Byzantines however could not prevent it from reaching Palermo, and were driven off by a squadron from the city under Muhammad ibn al-Sindi. Abu'l-Aghlab avenged himself by launching naval raids against Pantelleria and other localities, beheading the Christians taken prisoner. At the same time, a Muslim cavalry raid reached the eastern parts of the island around Mount Etna, burning the villages and crops and taking captives. In 836, Abu'l-Aghlab launched fresh attacks. A Muslim force seized the fortress known in Arabic as Qastaliasali (Castelluccio on the island's northern coast), but were driven away by a Byzantine counter-attack. The Muslim fleet, under al-Fadl ibn Yaqub, raided the Aeolian Islands and seized a number of forts on the northern coast of Sicily, most notably Tyndaris . In the meantime, another cavalry raid was dispatched against the region of Etna and was so successful that the price for Byzantine captives plummeted.
In 837, a Muslim army under Abd al-Salam ibn Abd al-Wahhab attacked Enna, but was defeated by the Byzantines, and Abd al-Salam himself was taken prisoner. The Muslims responded by reinforcing their position around Enna, which they placed under siege. During the following winter, one of the besiegers discovered an unguarded path leading to the town, allowing the Muslims to take the entire lower town. The Byzantines however managed to maintain control of the citadel, and after negotiations secured a Muslim withdrawal in exchange for a large ransom. Theophilos now undertook a serious effort to relieve Sicily: he assembled a large army and placed it under the command of his son-in-law, the Caesar Alexios Mousele. Mousele arrived in Sicily in spring 838, in time to relieve the fortress of Cefalù from a Muslim attack. Mousele scored a number of successes against Muslim raiding parties but, back in Constantinople, his enemies launched accusations of contacts with the Arabs and designs on the throne. Furthermore, the death of his infant wife, Maria, cut his link to Theophilos, and the Emperor sent the archbishop of Syracuse, Theodore Krithinos, to recall the Caesar to Constantinople in 839. On 11 June 838 the emir Ziyadat Allah had died, and was succeeded by his brother, Abu Iqal ibn al-Aghlab. The new emir sent fresh troops to Sicily, where the Muslims regained the upper hand after Mousele's departure: in 839–840, the Muslims captured the fortresses of Corleone, Platani, Caltabellotta, and possibly also Marineo , Geraci and other forts, and in 841, they raided from Enna as far as Grotte. In the same period, the Sicilian Muslims also established footholds in the Italian mainland. The Muslims were asked to assist the beleaguered Duchy of Naples against Sicard of Benevento in 839, but then they sacked Brindisi and, following Sicard's murder and the outbreak of civil war in the Principality of Benevento , seized Tarentum in 840 and Bari in 847, which they made their bases. Until well into the 880s, the Muslims would launch destructive raids along the coasts of Italy and into the Adriatic Sea from their bases on the Italian mainland most notably from the Emirate of Bari, until its destruction in 871.
In late 842 or 843, with Neapolitan support, the Muslims conquered Messina. In 845, the fortress of Modica also fell, while the Byzantines, now at peace with the Abbasid Caliphate, received reinforcements from the eastern theme of Charsianon. The two armies met near Butera, where the Byzantines suffered a crushing defeat, losing about 10,000 men. In the wake of this disaster, the Byzantine position deteriorated rapidly: al-Fadl ibn Ja'far took Leontini by a ruse in 846, and the fortress of Ragusa followed in 848, when its garrison was forced by severe famine to surrender it to the Muslims, who razed it to the ground. At about the same time (late 847 or 848), an attempt by the Byzantine fleet to land troops near Palermo failed, and subsequently the Byzantines lost seven out of their ten ships in a storm. In 851, the capable Muslim governor and general Abu'l-Aghlab Ibrahim died, and the local Muslims elected Abu'l-Aghlab al-Abbas ibn al-Fadl , the victor of Butera, as his successor. Without waiting for confirmation of his appointment from Ifriqiya, the new governor attacked and captured the northern fortress of Caltavuturo, and then turned south towards Enna, whose Byzantine commander refused to meet him in the field. Abbas continued his raid, and in 852–853 he devastated the Val di Noto. Butera was besieged for five or six months, until its inhabitants came to terms and secured his withdrawal by delivering 5,000–6,000 prisoners. Little details are known about the events of the next four years, but the picture painted by the sources is one of unopposed Muslim raids across the remaining Byzantine territories. Abbas captured several fortresses, including Cefalù in 857, whose population was allowed safe departure and which was then razed. Gagliano was also besieged, but not taken. In summer 858, the two sides were engaged in naval combat, probably off Apulia; Abbas' brother Ali managed to defeat the Byzantine fleet of 40 ships in the first engagement, but was in turn defeated and forced to flee in the second. Then, in January 859, the Muslims scored a major success through the capture, with the aid of a Byzantine prisoner, of hitherto impregnable Enna. As Metcalfe remarks, the capture of the fortress was of major importance, for Enna was the key to Muslim expansion in eastern Sicily: "without bringing it under their control, the Muslims were not able to capture and consolidate towns further to the eastwithout the risk of losing their gains in counteroffensives. ... Its fall, followed by its comprehensive sacking and the slaughter of its defenders on 24 January 859 was thus, in military terms, the crowning achievement of the early Aghlabids in Sicily since the fall of Palermo". The fall of Enna reduced the Byzantines to the eastern coastal strip between Syracuse and Taormina, and forced the emperor to send a large army and a fleet of reportedly 300 ships, under Constantine Kontomytes, which arrived at Syracuse in autumn 859. Soon after, the Byzantine navy was defeated a major battle with the Muslims, in which the Byzantines lost a third of their fleet. Nevertheless, the arrival of a large Byzantine army induced several settlements, which had previously submitted to the Muslims, to rise in revolt. Abbas soon suppressed these uprisings, and marched against Kontomytes. The two armies met near Cefalù, and in the ensuing battle, the Byzantines were heavily defeated and retired to Syracuse, while Abbas strengthened his position by refortifying and colonizing Enna.
Abbas died in autumn 861, after another raid into Byzantine territory, and was buried at Caltagirone; the Byzantines later exhumed and burned his corpse. As his replacement, the Sicilian Muslims chose his uncle Ahmad ibn Ya'qub. His tenure was short, as in February 862 he was deposed in favour of Abdallah, son of Abbas. Abdallah's general Rabah was able to capture a few Byzantine fortresses, despite suffering a defeat in battle at first. Abdallah's elevation, however, was not acknowledged by the Aghlabids, and he was replaced, after only five months in office, by Khafaja ibn Sufyan. In 863, Khafaja sent his son Muhammad to raid the environs of Syracuse, but he was defeated by the Byzantines and forced to retire. In February/March 864, however, with the aid of a Byzantine renegade, the Muslims captured Noto and Scicli. In 865, Khafaja led in person an expedition against the environs of Enna which may signify that the Byzantines had retaken it, or that they still held forts in its vicinity before moving onto Syracuse, but again his son Muhammad was defeated in an ambush, losing 1,000 men. In 866, Khafaja marched once more against Syracuse. From there he marched along the coast towards the north. There he met a delegation of the citizens of Taormina, who concluded a treaty with him, but soon broke it. In the same year, the Muslims retook Noto and Ragusa, which the Byzantines had apparently recaptured, or which had simply failed to renew their tribute payments after previous capitulations. Khafaja also captured the fortress called "al-Giran" and a few other towns, before an illness forced him to return to Palermo. In the summer of 867, after the illness had passed, Khafaja led his army towards Syracuse and Catania again, raiding their environs. In September 867, the Byzantine emperor Michael III was killed and succeeded by Basil I the Macedonian. The new emperor was more energetic than his predecessor, and the relative peace on his eastern frontier allowed him to soon turn his full attention to the west: in 868–869 admiral Niketas Ooryphas was sent to relieve an Arab siege of Ragusa and re-establish imperial authority in Dalmatia, after which he sailed to Italy in an abortive attempt to conclude a alliance through marriage and co-ordinate a joint siege of Bari with the western emperor, Louis II. Another fleet was dispatched to Sicily in spring 868, but the Byzantines were heavily defeated by Khafaja in battle, after which the Muslims freely raided the environs of Syracuse. After Khafaga's return to Palermo, his son Muhammad launched a raid against mainland Italy, possibly besieging Gaeta. On his return to Sicily, in January–February 869, Muhammad led an attempt to capture Taormina through treason, but although a small Muslim detachment gained control of the gates, Muhammad tarried to arrive with the main army and the detachment, fearing capture, abandoned the city. A month later, Khafaja launched an attack on the region of Mount Etna, probably against the town of Tiracia (modern Randazzo), while Muhammad raided around Syracuse. The Byzantines, however, sortied from the city and defeated Muhammad's men, inflicting heavy casualties, forcing Khafaja to turn on Syracuse himself. He reportedly laid siege to the city for a few weeks, before turning back towards Palermo in June. On his march home, however, he was assassinated by a dissatisfied Berber soldier, who then fled to Syracuse. It was a heavy loss for the Sicilian Muslims. The motives for the murder remain unclear: Metcalfe suggests a dispute over the division of spoils between the various sections of the Muslim army, but Alexander Vasiliev suggested the possibility that the Berber soldier was in the Byzantines' pay.
Khafaja was succeeded by his son Muhammad, elected by the Sicilian army and confirmed by the Aghlabid emir. In contrast to his previous energy, Muhammad was a sedentary governor, preferring to remain in his capital rather than campaign in person. His tenure was furthermore cut short when he was assassinated by his court eunuchs on 27 May 871. Nevertheless, his tenure is associated with a major success of long-term significance, the capture of Malta. Of all the islands around Sicily, this was the last to remain in Byzantine hands, and in 869 a fleet under Ahmad ibn Umar ibn Ubaydallah ibn al-Aghlab al-Habashi attacked it. The Byzantines, having received timely reinforcements, resisted successfully at first, but in 870 Muhammad sent a fleet from Sicily to the island, and the capital Melite fell on 29 August 870. The local governor was captured, the town was plundered Ahmad al-Habashi reportedly took along the local cathedral's marble columns to decorate his palace and its fortifications razed. The fall of Malta had important ramifications for the defence of what remained of Byzantine Sicily: with Reggio in Calabria and now Malta in their hands, the Muslims completed their encirclement of the island, and could easily interdict any aid sent from the east. From 872 to 877 there was apparently a period of calm, since the sources are silent on any military operations in Sicily. This was probably chiefly due to internal turmoil in Muslim Sicily, with six governors reported as having taken office during this period, as well as the weakness of the Aghlabid government on the Ifriqiyan metropolis. In Italy, Muslim raids continued, but the Byzantines had a major success in 875 or 876, after the death of Louis II, when they took possession of Bari. In 875, the unwarlike and pleasure-loving Aghlabid emir Muhammad II ibn Ahmad (r. 864–875) died, and was succeeded by his more energetic brother, Ibrahim II (r. 875–902). The new Emir of Ifriqiya was determined to finally capture Syracuse. He appointed a new governor for the island, Ja'far ibn Muhammad, and sent a fleet from Ifriqiya to his assistance. Ja'far began his campaign in 877, raiding the Byzantine territories and occupying some outlying forts around Syracuse, before settling down to besiege the city. The Muslims, well supplied with siege weapons, launched incessant attacks on the city's defenders, but Syracuse received scant reinforcements from Constantinople, where the bulk of the imperial fleet was apparently occupied with carrying building materials for a sumptuous new church built by Emperor Basil. During nine months of siege, the Arabs gradually occupied the outer defences, and finally, on 21 May 878, stormed the city. The population was massacred or enslaved, and the city thoroughly looted over two months.
The Byzantines tried to take advantage of the Arab revolt, and began assembling forces at Messina and Reggio, while a fleet was dispatched from Constantinople. Abu'l-Abbas, however, did not tarry and as soon as he had suppressed the rebellion, marched against the Byzantines, ravaging the environs of Taormina and launching an unsuccessful siege of Catania before returning to winter in Palermo. In the next spring, he resumed his attack and assaulted Demona. To disrupt the Byzantine preparations, his forces then crossed over to the mainland. Reggio was captured on 10 July, and was subjected to a savage sack; a vast booty was collected, over 15,000 of its inhabitants were carted off as slaves, and the jizya imposed on the remainder. On his return to Sicily, Abu'l-Abbas came across a Byzantine fleet that had just arrived from Constantinople and thoroughly defeated it, capturing thirty of its vessels. In early 902, Emir Ibrahim II was forced into abdication by his subjects, through the intervention of the Abbasid caliph. Ibrahim exchanged places with Abu'l-Abbas, who was named as his successor: Abu'l-Abbas left Sicily for Ifriqiya, while Ibrahim now resolved to take up the mantle of the Holy War, and accompanied a group of volunteers to Sicily in the summer. In an act that broke the long-standing stalemate on the island, Ibrahim and his followers advanced on Taormina, defeated the Byzantine garrison before its walls and laid siege to it. Left unsupported by the imperial government, the town fell on 1 August 902. Ibrahim then capitalized on his success by sending raiding parties against various strongholds in the vicinity, forcing either their capitulation and destruction or the payment of tribute. Indefatigable, Ibrahim now crossed over into the mainland, where cities as far as Naples began to prepare to resist his attack. In the end, his advance was stopped at the siege of Cosenza , where Ibrahim died of dysentery on October 24. His grandson stopped the military campaign and returned to Sicily. Although few strongholds in the northeast remained unconquered and in Christian hands, the fall of Taormina marked the effective end of Byzantine Sicily, and the consolidation of Muslim control over the island. However, it did not signal the end of Arab–Byzantine warfare on and around the island. The long Arab–Byzantine struggle left abiding traces on the island's subsequent history: although under Muslim rule, Sicilian culture quickly became Arabicized, the Christian communities in the central and eastern parts largely resisted islamization. The level of Arab influence, as attested through surviving toponyms, also varied across the island depending on the length of resistance and the extent of Arab settlement: there are many Arab-derived names in the western third (the medieval Val di Mazara), are more mixed in the southeastern third (Val di Noto ), while Christian identities survived strongest in the northeastern third of the island (Val Demone), which was the last to fall, where Christian refugees from other parts of Sicily had assembled, and which furthermore remained in contact with Byzantine southern Italy.