Between the Viking Age and the Middle Ages, there was a noticeable change in relations between Scandinavia and the Islamic world – the sources point to a shift from travel and trade to hostility and war. Muslims did not settle in the North until the eighteenth century, and during the Middle Ages there was little contact between Scandinavians and ‘real’ Muslims. So how did Danes and Swedes imagine and describe this Other? Is there anything unusual or unexpected about the portrayal of Muslims? How does this image compare to that of the other great religious opponent, the Jew? By investigating East Norse devotional texts, travel literature, saints’ lives, romances and accounts of Ottoman warfare, this paper aims to draw out some of the major themes in medieval Scandinavian descriptions of Muslims and Islam.