Between 780–1180, the Byzantine Empire and the Abbasid and Fatimid caliphates in the regions of Iraq, Palestine, Syria, Anatolia and Southern Italy fought a series of wars for supremacy in the Eastern Mediterranean. After a period of indecisive and slow border warfare, a string of almost unbroken Byzantine victories in the late 10th and early 11th centuries allowed three Byzantine Emperors, namely Nikephoros II Phokas, John I Tzimiskes and finally Basil II to recapture territory lost to the Muslim conquests in the 7th century Arab–Byzantine wars under the failing Heraclian Dynasty.

Consequently, large parts of Syria, excluding its capital city of Damascus, were taken by the Byzantines, even if only for a few years, with a new theme of Syria integrated into the expanding empire. In addition to the natural gains of land, and wealth and manpower received from these victories, the Byzantines also inflicted a psychological defeat on their opponents by recapturing territory deemed holy and important to Christendom, in particular the city of Antioch—allowing Byzantium to hold two of Christendoms' five most important Patriarchs, those making up the Pentarchy.

Nonetheless, the Arabs remained a fierce opponent to the Byzantines and a temporary Fatimid recovery after c. 970 had the potential to reverse many of the earlier victories. And while Byzantium took large parts of Palestine, Jerusalem was left untouched and the ideological victory from the campaign was not as great as it could have been had Byzantium recaptured this Patriarchal seat of Christendom. Byzantine attempts to stem the slow but successful Arab conquest of Sicily ended in a dismal failure. Syria would cease to exist as a Byzantine province when the Turks took the city of Antioch in c. 1084. The Crusaders took the city back for Christendom in 1097 and established a Byzantine protectorate over the Crusader Kingdoms in Jerusalem and Antioch under Manuel I Komnenos. The death of Manuel Komnenos in 1180 ended military campaigns far from Constantinople and after the Fourth Crusade both the Byzantines and the Arabs were engaged in other conflicts until they were conquered by the Ottoman Turks in the 15th and 16th centuries, respectively.

Background, 630–780 In 629, conflict between Byzantine Empire and Arabs started when both parties confronted in the Battle of Mu'tah. Having recently converted to Islam and unified by the Islamic Prophet's call for a Jihad (struggle) against the Byzantine and Persian Empires, they rapidly advanced and took advantage of the chaos of the Byzantine Empire, which had not fully consolidated its re-acquisitions from the Persian invasions in c. 620. By 642, the Empire had lost Egypt, Palestine, Syria and Mesopotamia. Despite having lost two-thirds of its land and resources (most of all the grain supply of Egypt) the Empire nonetheless retained 80,000 troops, thanks to the efficiency of the Thema system and a reformed Byzantine economy aimed at supplying the army with weapons and food. With these reforms, the Byzantines were able to inflict a number of defeats against the Arabs; twice at Constantinople in 674 and 717 and at Akroinon in 740. Constantine V, the son of Leo III (who had led Byzantium to victory in 717 and 740) continued the successes of his father by launching a successful offensive that captured Theodosioupolis and Melitene. Nonetheless, these conquests were temporary; the Iconoclasm controversy, the ineffective rule of Irene and her successors coupled with the resurrection of the Western Roman Empire under the Frankish Carolingian Empire and Bulgarian invasions meant that the Byzantines were on the defensive again.

Period of 780–842

Michael II vs Caliph Al-Ma'mun Between 780 and 824, the Arabs and the Byzantines were settled down into border skirmishing, with Arab raids into Anatolia replied in kind by Byzantine raids that "stole" Christian subjects of the Abbasid Caliphate and forcibly settled them into the Anatolian farmlands to increase the population (and hence provide more farmers and more soldiers). The situation changed however with the rise to power of Michael II in 820. Forced to deal with the rebel Thomas the Slav, Michael had few troops to spare against a small Arab invasion of 40 ships and 10,000 men against Crete, which fell in 824. A Byzantine counter in 826 failed miserably. Worse still was the invasion of Sicily in 827 by Arabs of Tunis. Even so, Byzantine resistance in Sicily was fierce and not without success whilst the Arabs became quickly plagued by the cancer of the Caliphate— internal squabbles. That year, the Arabs were expelled from Sicily but they were to return.

Theophilos vs Caliphs Al-Ma'mun and Al-Mu'tasim In 829, Michael II died and was succeeded by his son Theophilos. Theophilos received a mixed diet of success and defeat against his Arab opponents. In 830 AD the Arabs returned to Sicily and after a year-long siege took Palermo from their Christian opponents and for the next 200 years they were to remain there to complete their conquest, which was never short of Christian counters. The Abbasids meanwhile launched an invasion of Anatolia in 830 AD. Al-Ma'mun triumphed and a number of Byzantine forts were lost. Theophilos did not relent and in 831 captured Tarsus from the Muslims. Defeat followed victory, with two Byzantine defeats in Cappadocia followed by the destruction of Melitene, Samosata and Zapetra by vengeful Byzantine troops in 837. Al-Mu'tasim however gained the upper hand with his 838 victories at Dazimon, Ancyra and finally at Amorium—the sack of the latter is presumed to have caused great grief for Theophilos and was one of the factors of his death in 842.

Campaigns of Michael III, 842–867 Michael III was only two years of age when his father died. His mother, the Empress Theodora took over as regent. After the regency had finally removed Iconoclasm, war with the Saracens resumed. Although an expedition to recover Crete failed in 853, the Byzantine scored three major success in 853 and 855. A Byzantine fleet sailed unopposed in Damietta and set fire to all the ships in the harbour, returning with many prisoners. Better still for Constantinople was the desperate and futile defense by the Emir of Melitene, whose realm was lost by the Arabs forever. Insult was added to injury for the Arabs when the Arab governor of Armenia began losing control of his domain. After the 9th century, the Arabs would never be in a dominant position in the East.

In the West however, things went the Saracen way; Messina and Enna fell in 842 and 859 whilst Islamic success in Sicily encouraged the warriors of the Jihad to take Bari in 847, establishing the Emirate of Bari which would last to 871. In invading southern Italy, the Arabs attracted the attention of the Frankish powers north.

Michael III decided to remedy the situation by first taking back Crete from the Arabs. The island would provide an excellent base for operations in southern Italy and Sicily or at the least a supply base to allow the still resisting Byzantine troops to hold out. In 865 Bardas, maternal uncle to Michael III and one of the most prominent members of his regency, was set to launch an invasion when a potential plot against his wife by Basil I and Michael III (the former being the future emperor and favorite of the latter) was discovered. Thus Islamic Crete was spared from an invasion by Byzantium's greatest general at the time.

Campaigns of Basil I and Leo VI, 867–912

Basil I

Like his murdered predecessor, the reign of Basil I saw a mixture of defeat and victory against the Arabs. Byzantine success in the Euphrates valley in the East was complemented with successes in the west where the Muslims were driven out of the Dalmatian coast in 873 and Bari fell to the Byzantines in 876. However, Syracuse fell in 878 to the Sicilian Emirate and without further help Byzantine Sicily seemed lost. In 880 Taranto and much of Calabria fell to Imperial troops. Calabria had been Rome's pre-Aegyptus bread basket, so this was more than just a propaganda victory.

Leo VI Basil I died in 886, convinced that the future Leo VI the Wise was actually his illegitimate son by his mistress Eudokia Ingerina. The reign of Leo VI rendered poor results against the Arabs. The sack of Thessalonika in 904 by the Saracens of Crete was avenged when a Byzantine army and fleet smashed its way towards Tarsus and left the port, as important to the Arabs as Thessalonika was to Byzantium, in ashes. The only other notable events included the loss of Taormina in 902 and a six-month siege of Crete. The expedition departed when news of the Emperor's death reached Himerios, commander of the expedition, and then it was almost completely destroyed (Himerios escaped) not far from Constantinople.

Romanos I and Constantine VII, 920–959 Until this time, the Byzantine Empire had been concerned solely with survival and with holding on to what they already had. Numerous expeditions to Crete and Sicily were sadly reminiscent of the failures of Heraclius, even though the Arab conquest of Sicily did not go according to plan. After Leo's death in 912 the Empire became embroiled in problems with the regency of the seven-year-old Constantine VII and with invasions of Thrace by Simeon I of Bulgaria.

The situation changed however when the admiral Romanos Lekapenos assumed power as a co-emperor with three of his rather useless sons and Constantine VII, thus ending the internal problems with the government. Meanwhile, the Bulgar problem more or less solved itself with the death of Simeon in 927, so Byzantine general John Kourkouas was able to campaign aggressively against the Saracens from 923 to about 950. Armenia was consolidated within the Empire whilst Melitene, which had been a ruined emirate since the 9th century, was annexed at last. In 941 John Kourkouas was forced to turn his army north to fight off the invasion of Igor I of Kiev, but he was able to return to lay siege to Edessa—no Byzantine army had reached as far since the days of Heraclius. In the end the city was able to maintain its freedom when Al-Muttaqi agreed to give up a precious Christian relic: the "Image of Edessa".

Constantine VII assumed full power in 945. Whilst his predecessor, Romanos I had managed to use diplomacy to keep peace in the West against the Bulgars, the East required the force of arms to achieve peace. Constantine VII turned to his most powerful ally, the Phocas family. Bardas Phokas the Elder had originally supported the claims of Constantine VII against those of Romanos I, and his position as strategos of the Armeniakon Theme made him the ideal candidate for war against the Caliphate. Nevertheless, Bardas was wounded in 953 without much success, though his son Nikephoros Phokas was able to inflict a serious defeat on the Caliphate: Adata fell in 957 whilst Nikephoros' young nephew, John Tzimiskes, captured Samosata in the Euphrates valley in 958.

Romanos II, 959–963 Romanos II launched the largest expedition by Byzantium since the days of Heraclius. A mammoth force of 50,000 men, 1,000 heavy transports, over 300 supply ships, and some 2,000 Greek Fire Ships under the brilliant Nikephoros Phokas set sail for Candia, the Islamic capital of Crete. After an eight-month siege and a bitter winter, Nikephoros sacked the city. News of the reconquest was met with great delight in Constantinople with a night-long service of thanksgiving was given by the Byzantines in the Hagia Sophia.