The Middle Ages can be said to begin as Mohammed’s successors began to conquer weary, disease-struck regions of the Eastern Roman Empire, and to end as the Muslim-convert Turks finally brought down the walls of Eastern Rome itself: Constantinople. Contact with Muslims and other peoples who lived under Muslim rule gave medieval Europe much of its cultural flavor, even when that contact was hostile. (Charlemagne’s grandfather, for example, won prominence over the titular king by defeating invading Arabs; not to mention the Crusades!)
The full Muslim Empire influence on food wasn’t felt at first in the heart of Europe, but it was a steady influence that grew with each century. It consisted of importation of Asian foods and, more profoundly, the transplantation of Asian crops to parts of Europe where they could survive.
The spice trade was the first obvious influence. Spices from the far east (India and its islands; Malaysia and Indonesia; China) had been carried on the Silk Road and by ship since Roman times. But after the Caliphs conquered most of Alexander the Great’s old empire, trade sped up, at least within the empire. It wasn’t always easy to get these goods outside the empire; the Mediterranean at times was a Muslim lake, hostile to Western ships entering its trading ports. But the transfer of spices and other exotic products between India and Syria sped up and became routine. When the First Crusade established a European zone in Middle Eastern ports, the spice trade with northern Europe really took off.
At the height of Outremer, the Crusader kingdom, exotic eastern spices were not only common but extremely plentiful in royal, aristocratic and wealthy monastic kitchens. The #1 spice: black pepper. (By the Renaissance, its price had dropped to where wealthy craftsmen could afford it, so it lost its social cachet among the elite.) Closely following: cinnamon, ginger, cloves, mace and cardamom.
Sugar cane was an Asian import, too. Arabs established the first European refinery on the island of Crete; refined sugar, in Arabic, was “qandi.” The 14th-century Crusader kingdom on Cyprus also refined sugar. Venice shipped sugar to the rest of Europe at exorbitant prices, and eventually sugar plantations in the Canary Islands began the practice of African slavery.
Arabs invented caramel and nougat, the first real candies (caramel was also used for hair removal). One of their basic culinary rules was to copy whatever Mohammed had personally liked to eat, and Mohammed apparently had a real sweet tooth. The earliest forms of what we recognize as dessert foods developed in Muslim cooking zones. (No wonder we all love baklava.)
Asian plants came to Europe first by way of Spain, the Arab outpost. The Syrian dynasty who first ruled in Andalusia transplanted date palms, sugar cane, citrus trees (oranges and lemons) and pistachio nuts. Watermelon, eggplant and asparagus seem also to be Asian transplants around this time.
Last but not least, rice was a new grain crop imported from Asia. It caught on in Italy, but remained an exotic food for the wealthy until the close of the medieval period.