Don't forget Islam; Muhammad lived from 570-632, (this is a generally accepted date; there's some waffling sometimes about the birth).The first Caliph was Abu Bakr in 632, when Islam mostly a faith of the Bedouin. About ten years later, during the reign of Abu Bakr's successor, Umar, (634-644) All of Palestine, Syria and everything but a few tiny pockets of the former Persian empire was under Muslim control. By 956 the Seljuk Turks not only accepted Islam, they actively embraced and evangelized Islam.
Keep in mind that the Islam religious and social powers, while evangelical, did not prohibit or otherwise restrict other religions; you've got Christians, Jews, Muslims, and Zoroastrianism, the "forgotten" medieval religion, living side by side. By 720 all of the modern Middle East (but not Asia minor) all of North Africa, and most of Spain was under Islamic political and social control--though other religions still flourished, they were social and political minorities; the language was Arabic, and the faith Islamic.
This is pretty standard intro to Medieval History stuff; I'm cribbing from my own lecture notes. See if you can find an undergraduate Medieval history text book; they tend to have just the sorts of maps you're looking for. My personal favorite is Medieval Western Civilization and the Byzantine and Islamic Worlds, by Deno J. Geanakoplos, because it does cover the fact that Yes Virginia, There Were Other Religions.
Also keep in mind that Iceland was a little slow to convert. There was a sort of mixed Pagan Norse/Christian thing happening for a very long time, as the early settlement included Vikings and Christian hermits, and you read about people offering blood sacrifices at the foot of a cross, and the like.