One theory I've heard (I forget where) about why Europe did so well as compared to the Middle East is that
the Middle East got pillaged by the Mongols in the 1200s and never really recovered, whereas Europe got off relatively easy, pillaging-wise, and even had some
semi-friendly relations with the Mongols. So my POD is that, in 1218, instead of executing Genghis Khan's ambassadors, the governor of Otrar welcomes them with open arms, beginning an amicable relationship of trade, cultural dialogue, and relatively few severed heads between the Mongol Empire and the Islamic world. Instead, the Mongols turn to Europe, penetrating as far as the North European Plain will take them, shattering Novgorod, Poland and the Holy Roman Empire. The conquests weren't permanent; the Golden Horde was overstretched and surrounded by enemies in Central Europe, and eventually pulled back to more easily defensible borders in Western Russia, contenting itself with setting up tributary states in Central and Eastern Europe.
The Crusaders, wavering in the face of Islamic opposition anyway, are swiftly recalled to the home front. Eventually the Teutonic Knights retake Northern Germany from the Mongolian vassals, and the Holy Roman Empire is replaced by Teutonic-allied kingdoms (except for a rump HRE on the Rhine), as the Mongolian Peril to the east necessitates a higher degree of political unity. England, being an island immune from Mongol cavalry invasion, does fairly well, and carves out new domains in western France. Genoa takes control of many important Mediterranean trade routes and also does well.
However, in general, Europe is a horrible mess. With morale low and treasuries emptied to hold off the Mongols and fight the futile Crusades, Europe is easy prey for the Islamic sultanates, which are undergoing a renaissance in culture and a boom in economic and military power. The Christians are driven out of Sicily and Spain, and the Byzantines crumble before the might of the Seljuks. Eventually the Emir of Tunis, an ambitious young would-be conqueror whose grandfather had taken Sicily, and whose father had taken southern Italy up to Naploli, announces a new crusade, one aimed at Rome. The stated reasons are three. Firstly, to convert the Italians to Islam. Secondly, to wrest control of the Western Mediterranean trade routes from Genoa. Thirdly, to save from Christian neglect and barbarism the treasures of Rome itself. The entire Islamic world is, at the time, rediscovering the works of antiquity, and have a great interest in possessing Rome. In 1312, the Emirate of Tunisia captures Rome, with the Pope fleeing to Milan in haste before the heathen army. The Emir installs himself in the city and crowns himself Emperor. People begin to suspect the man is eccentric.
In 1347, the year of this map, the situation is as follows. The Roman Sultanate (as its Islamic allies insist on calling it despite its claims of being an "Imperium") is a major trade power and also a patron of the classics and history. It is even said, only half-jokingly, that its protectorates in Greece are largely there to dig up old amphorae for the Emir/Emperor. The Seljuks are a real superpower (they stretch to Persia), and the Egyptians and Moors are also strong. All four are nominally part of one Caliphate, although the Caliph, like the old Pope, is really only a spiritual leader with some land in the Hejaz.
Europe is a chaotic place to say the least. There are three popes (yes,
deja-vu), each calling the other two antipopes. Christian fanaticism is widespread, and in the Teutonic Order-State, institutionalized as a foaming-at-the-mouth witch-burning theocracy. Despite this, heresy and even open paganism are widespread. The
Cathars have carved a state out of the mess of Greater France, and are even sending out secret missionaries to spread their Gnostic ideas and oppose the designs of the Rex Mundi, the Cathar Satanic figure and creator of the (evil) world, whom they identify with the Christian God and Muslim Allah. The Lithuanians are also still pagan, and still going strong as a Mongol ally. There are even rumors that the Scandinavians are sliding back into Wodenism in hidden ceremonies in remote fjords, a rumor supported by a string of recent church-burnings in Norway.
Many Europeans are beginning to question whether life has to be this way, and disconcerting tales are reaching the crowned heads of Europe, speaking of their Christian subjects leaving their farms in the night and striking out for the borders of Dar al-Islam, or of entire merchant ships being taken by mutiny and sailed into Muslim ports. The flood of new literature from the Muslims' printing presses surely isn't helping matters.
Map to follow.
EDIT: (Note: the Mongol's vassals are all Christian, "some nominally Christian" is intended to be some in-world European bias creeping in, as the dogmatic Catholic powers do not see Eastern Orthodox Novogord, diverse and tolerant Kiev, and Papal Schism-neutral Hungary as "true Christians")