For the entirety of the Middle Ages the Byzantine Empire bordered on a variety of Islamic polities, sometimes only small emirates and at other times giant empires that dwarfed it in size and resources. Pretty much no human society can live in a state of constant war with its neighbours and so it is no surprise that Byzantine-Islamic relations were also much more complicated and multi layered than that. The Byzantines were usually very well informed about the different schisms and rivalries among the Islamic powers and were perfectly willing to take advantage of them. Besides fighting both sides also engaged in highly sophisticated diplomatic activities and a lively trade of goods and ideas. People, goods and cultural practices regularly bridged the frontier between Christian and Muslim lands. And as we’re talking about roughly eight centuries of shared history, well … get ready for a wall of text.

Byzantium and the Arab Caliphate

During the early Middle Ages Byzantium faced only one, albeit massive Islamic realm, the early Arab Caliphate, ruled at first by Muhammad’s immediate successors, the four Rashidun Caliphs (632-661 AD), then by the Umayyad dynasty (661-750 AD) and last but not least the Abbasid dynasty (750-1258 AD). At least until the early 8th century AD this empire had not only overtaken East Rome’s most valuable provinces but was also firmly committed to conquering the rest. But even then it was impossible for the Muslim armies to constantly sustain their attacks on Byzantium. In fact the Caliphate was often highly unstable and at several times wrecked by civil wars, some of which triggered the dynastic changes just described. In those times of crisis Muslim authorities saw no other choice but to take up negotiations with Constantinople. When pressure was high enough they even might be forced to pay tribute to the emperor. One interesting example of compromise between both sides was the governance of the island of Cyprus. Located right between both empires no side could manage to hold complete control over the isle. Instead they reached an agreement in 688 AD to jointly rule it as an Arab-Byzantine condominium and split the revenues between themselves. This arrangement lasted for three centuries even while the wars on neighbouring Anatolia continued. The rivalry between the two powers also meant that any group that had fallen out with one of them could be sure to find safe haven with the other. For example in the 7th century AD parts of a Christian Arab tribal grouping, the banu Taghlib, sought refuge in the Byzantine Empire. Later in the same century a group of Slavs who had been forcefully relocated from the Balkans to the Arab frontier were understandably unhappy with their situation and switched sides to the Caliphate. There was also cultural exchange between both imperial centres. Later sources tell us for example that the Umayyad Caliph al Walid I (705-715 AD) requested Byzantine artisans from the emperor to embellish his religious foundations. Looking at the gold ground mosaics in major Umayyad monuments like the Dome of the Rock in Jerusalem or the Great Mosque of Damascus such a claim does not seem implausible.

After the failed siege of Constantinople in 718 AD the mortal danger for the Byzantine Empire ended although Arab attacks on Anatolia still continued regularly. Under the reign of the early Abbasids in the 8th and 9th century AD diplomatic missions were regularly exchanged between Constantinople and the recently founded Baghdad. This 12th century miniature from the Madrid Skylitzes shows one on which the patriarch John the Grammarian was sent from emperor Theophilos (829-842 AD) to caliph al Ma’mun (813-833 AD). Reportedly the emperor was so impressed by John’s description of the Abbasid residence in Baghdad that he ordered the building of the Bryas palace at the shores of the Sea of Marmara that copied the Islamic model in form and style. Unfortunately nothing of that structure remains. Another Byzantine ambassador reportedly procured the permission by the caliph al Mahdi (775-785 AD) to build a mill at Baghdad and even a loan of the needed funds. Its revenues were forwarded to him every year until his death when the property reverted to the caliph. Apparently water works were one area where the Abbasids could actually learn a thing or two from Byzantium because yet another 8th century ambassador had some scathing criticism for the newly founded Baghdad’s water supply. Caliph al Mansur (754-775 AD) understandably dismissed those shots against his prestigious new foundation at first but then acted on the envoy’s advice later any way. Abbasid-Byzantine rivalry on the field of sciences could be almost as intense as on the battle field. For example emperor Theophilos and caliph al Ma’mun engaged in a kind of bidding war for the services of the famed philosopher Leo the Mathematician, a contest which the emperor ultimately won. Of course diplomats and other travellers between both powers also engaged in trade. Precious textiles from the Islamic east were highly sought after among the elite of Constantinople. One courtier reportedly even jumped from his seaside palace into a merchants boat to acquire a matching set of brightly coloured rugs, bolsters and cushions from Syria before anyone else.

The Breakup of the Caliphate

The slow breakup of the Arab Caliphate into smaller Islamic polities, which already begun in the 8th century, opened up new opportunities for Byzantine diplomacy. In the early 9th century Constantinople reached out to the Umayyad emirs of Cordoba, descendants of the dynasty which the Abbasids had toppled in the east. Conveniently they were not only at odds with their ancestral rivals in Baghdad but also with the Frankish Empire which in turn threatened Byzantine possessions in the Adriatic. This again would draw the Frankish emperor Charlemagne (768-814 AD) and the Abbasid Harun al Rashid (786-809 AD) closer together. In medieval power politics Christian and Muslim rulers could easily ally with each other against their co-religionists if it proved necessary. The Byzantines retained good relations with Cordoba as both sides were located too far away from each other to have many clashing interests. In the 10th century envoys of emperor Constantine VII Porphyrogennetos (913-959 AD) arrived at the Umayyad court with an Arabic-Greek letter written in golden script on blue parchment. Similarly adorned texts have survived in a few instances like with the 9th century Codex of Theodora or the famous Blue Qur’an from around 900 AD. The precious gift should convince the caliph Abd ar-Rahman III (912-961 AD) to join forces with Constantine against the new rising power in the Mediterranean, the Fatimid Caliphate of North Africa. The alliance came to pass but unfortunately the Byzantine and Umayyad fleets were still beaten by Fatimid forces which forced Constantinople to the negotiating table with their North African foes.Both sides would frequently clash in the future but could also find common ground in their shared enmity towards the Abbasids of Baghdad. After the Fatimid caliph al Mu’izz (953-975 AD) had conquered Egypt from vassals of the Abbasids in 969 AD envoys from Byzantium congratulated him by gifting him a richly adorned saddle which reportedly had once belonged to Alexander the Great. The allusion to Alexander was a smart move to bridge the religious divide between Christians and Muslims since the great Macedonian was an admired role model for Byzantine and Islamic rulers alike.

In the meantime Abbasid power had almost completely broken down. All over their former provinces rose newly independent emirates that only acknowledged Abbasid suzerainty on paper. In time this allowed the Byzantines to again go on the offensive. Smaller polities like the emirate of Tarsus were conquered outright while others like the more powerful Hamdanids of Aleppo were eventually forced into vassalage. The emirs of Aleppo were even granted high ranking court titles. Those wars brought many Muslim prisoners to Constantinople. They didn’t necessarily languish in dark dungeons though. The highest ranking ones even participated in court ceremonies at the imperial palace and were gifted valuable presents to overawe them with the emperor’s magnanimousness. Other Muslim residents of Constantinople had come as traders. The 10th century ‘Book of the Eparchs’ mentions a special guild that dealt with imports from ‘Syria’ (the Abbasid Caliphate) which had to cooperate with Syrian merchants who have been domiciled in this city (Constantinople) for at least ten years. Muslims appear to have been a thriving minority in the city that even had access to their own mosques.

#Alliances between ERE and her Muslim neighbours

As far as I know, the ERE and her neighbouring Muslim Caliphates never actually joined hands against any enemies. There were of course diplomatic embassies exchanged, Constantinople supporting Fatimids of Egypt against Abbasids of Baghdad diplomatically, Trade etc but there never was a moment when they joined forces against a common foe.

That is of course not counting the time when Roman Navy ferried shattered Ottoman soldiers to the European side of the Empire after Timurlane destroyed Beyezid I at Ankara. The Emperor Manuel II is reported to have said "I prefer an enemy I know (Ottomans) than an enemy I don't (Timur)". But of course it was hardly altruistic, The ferried troops were supporters of the brothers of Prince Mehmed Celebi who wanted the throne for themselves and Romans were happy to prolong the Ottoman interregnum. That is not the only time Romans interfered in Politics of Ottoman Empire in support of pretenders. But of course we can't consider proxy wars or support for pretenders as Alliance between two states.

#Interaction between Religious and Scholarly figures

Greek works of science and philosophy were widely popular, translated and expanded on in the Islamic World so it might not be entirely out of question that scholars from the neighbouring empires may have corresponded with each other but however I am not aware if it ever happened.

For Religious figures, yes we have record of that. Orthodox Patriarch Nikolas Mystikos wrote to Sunni Caliph Al-Muqtadir denying the rumours in Baghdad that Mosque in Constantinople had been shut down and protesting the closure of Christian Churches in Abbasid Empire based on that rumour (Src: Jenkins, R.J.H.- Westerink, L.G. (eds.), Nicholas I. Letters (Washington DC 1973), no. 102.). He wrote another letter as well which went like:

Two Sovereignties, That of Arabs and of Byzantines, surpass all sovereignties in the world, like the two shining lights in the firmament. For this one reason, if no other, they should be partners and brethren. We ought not, because we are separated in the ways of our lives, our customs and our worship, to be altogether divided nor should we deprive ourselves from communication with one another in default of meeting each other in person. That is the way we ought to think and act, even if no necessity of our affairs compelled us to it. (Src: Muslim perception of other religions by Professor Jacques Waardenburg)

This letter shows the seriousness in the efforts made to reconcile the two rivals and one can speculate that such efforts may have resulted in treaties bringing more rights to their brothers in faith in their rivals' territory.

#Presence of Muslim Traders in Constantinople

The presence of Muslim merchants in Constantinople was continuous at the city's heyday, from the 9th century (if not earlier) up to the 12th century. You have to note, Islamic Prophet himself embarked on a trade trip to Roman Empire when he was young (Although he reportedly went back midway). Whether the presence of Muslim merchants was accompanied by a permanent installation of some of them (as it happened with the Venetians and the Genoese) is uncertain, but even their transitory presence was continuous and regularly renewed. We have already talked about the Mosque of Constantinople which was presumably built by the Romans for Prisoners of War and afterwards used by the traders until its destruction by the Latins after 4th crusade. It was restored when the Romans took the city back but ultimate fate of the Mosque is unknown.

Moreover, apart from the Arab merchants, by the 11th century the Muslim presence of Constantinople also comprised the Turkish element. A poem in the vernacular by John Tzetzes (mid-12th century) is indicative regarding this element, since it mentions that a great number of languages spoken in the markets of Constantinople, including the Arabic and the Turkish. (Source: Ζακυθηνός, Δ.Α., Βυζαντινή Ιστορία, 324-1071 (Athens 1972), pp. 386, 488.)

The Poem is transcribed below, as it was (Which is anti-Semitic but it serves our purposes as it mentions Arabic, Persian (At that point Muslim nation) and Turkish), From the book Byzantium: The Surprising Life of A Medieval Empire:

One finds me Scythian among Scythians, Latin among Latins,

And among any other tribe a member of that folk.

When I embrace a Scythian I accost him in such a way:

"Good day, my lady, good day, my lord: Salamalek alti, salamalek altugep."

And also to Persians I speak in Persian:

"Good day, my brother, how are you? Where are you from, my friend? Asan khais kuruparza khaneazar kharandasi?"

To a Latin I speak in the Latin language:

"Welcome, my lord, welcome, my brother: Bene venesti, domine, bene venesti, frater.

Where are you from, from which theme [province] do you come? Unde es et de quale provincia venesti?

How have you come, brother, to this city? Quomodo, frater, venesti in istan civitatem?

On foot, on horse, by sea? Do you wish to stay? Pezos, caballarius, per mare? Vis morare?"

To Alans I say in their tongue:

"Good day, my lord, my archontissa, where are you from? Tapankhas mesfili khsina korthi kanda," and so on.

If an Alan lady has a priest as a lover, she will hear such words:

"Aren't you ashamed, my lady, to have a love affair with the priest? To farnetz kintzi mesfili kaitz fua saunge."

Arabs, since they are Arabs, I address in Arabic:

"Where do you dwell, where are you from, my lady? My lord, good day to you. Alentamor menende siti mule sepakha."

And also I welcome the Rus according to their habits:

"Be healthy, brother, sister, good day to you. Sdra, brate, sestritza," and I say "dobra deni."

To Jews I say in a proper manner in Hebrew: [Anti Semitic bile that I have omitted due to its irrelevance and because its nonsense]

So I talk with all of them in a proper and befitting way; I know the skill of the best management."

What must be noted here is that in the beginning, the Muslim presence was mainly Arab. Turks did not appear on the steering until end of the Latin Empire and beginning of Turk dominance on traditionally Muslim domains of Levant and Near East. Turkish Sultanates such as Seljuqs of Anatolia did exist before that but at that time they were mere settlements and not the real driving power in Islamic world.

By the time the House of Osman (Ottoman dynasty) had established itself firmly in Anatolian Beyleks, Turkish Muslims in Constantinople had formed a regular Byzantine community. It is implied by the demand of Sultan Bayazid to appoint a Turkish judge in the city, who would attend to the judicial affairs of Turkish resident & subsequently in the description of the defensive measures taken by the Byzantines before the siege of 1453, when they sealed the gates of the walls and arrested any Turks who were caught inside the city. (Bekker, Ι. (ed.), Michaelis Ducae Nepotis Historia Byzantina (Bonn 1834), ΧΙΙΙ p. 49, XV p. 56 and XXXIV pp. 244-245.)

Note: Most of this is taken from my answer on History Stack Exchange. Just putting this notice so that I am not accused of copy-pasta from my own answer.