I would guess most likely with no Islam, Antolia would be some kind of Orthodox, Russian or Greek because of the Byzantines. However, the Byazantines might not fall, just reduced to a minor power of OTL Greece and Turkey. Zoroarainism would rise as a minor foothold in Southern Perisa, and might eventually lead to a civil war if Christianity doesn't influence the area enough. Expect no United Arabia, or no North African caliphate.

I would also expect higher tensions within Christianity, becuase there was No Islam for no common enemy for them to agree on relate.

Without Islam there would probably be Zoroastrian dominance in the Middle East like Iran, Uzbekistan, Turkmenistan and Afghanistan, i also think that the Byzantine Empire wouldn't collapse, as No Islam = No Ottoman Empire, i think that Buddhism and Confusianism would be popular in Indonesia and other muslim countries.

Without Islam the Byzantine empire wouldn't fall but it would still be weakened eventually, Coptic and Nestorian rebellions would happen due to discontent with the orthodox favoritism and most of the history would be the same (but a levantine "reconquista" instead) the middle east and the Caucasus as well as a good portion of central Asia would be Zoroastrian, Arabia would be divided between Arab paganisms, Judaism in a few areas, Christianity in others and Zoroastrianism. North Africa would be subject of Arianism and Catholicism fighting for the area and Moorish invasions while eastern Europe would be a conflict area of local paganisms, tengrism and Catholicism, maybe Zoroastrianism. but quite in general

I wonder if theZunbil religion could have survived.

Don't mistake CK2 for actual history; the followers of Zun were pretty few and far between in OTL (worshipped primarily by the aristocracy) with the majority of the population in the regions following the stands of Hinduism. Without Islam, the Zunbil faith is still almost certainly going to be displaced by another faith depending on which powers Afghanistan moves towards. If they swing towards India, you would expect Hindu/Buddhist practices becoming more ingrained within the local ruling class, but if they moved towards Persia (and depending on which way it swings without Islam), you would expect either the Zoroastrian or Christian faiths to come out on top.

First of all, thanks for all the contributions. Really are very interesting for discussions.

Sine dei gloriem: as Spaniard I have to recognize that the discussion about the Iberian Peninsula is essential not only for Europe, but also the Americas.Well, from the late 7th century there was a division between the Visigothic clans and the Visigothic kingdom was in decline due to plague, famine and drought that provoked a significant loss of population (demographic crisis). The scene at the beginning of the 8th century was of a very weak Visigothic kingdom plunged in a civil war. In addition, it is known that the faction of the nobility of Witiza's descendants helped the Moorish initially. Indeed, Toledo was conquered in less than a year since the invasion and in the southeastern peninsula (present-day Murcia and Valencia) the count Theudimer swore allegiance to the Muslim emir Abd al-Aziz ibn Musa.On the other hand, Visigothic law was very hostile against the Sephardic Jews of the Iberian Peninsula and they look favorably not only the Muslims, but also the Moorish because they professed Judaism for proselytizing and miscegenation.

Thus, I imagine an unified strong Moorish power whose melting-pot originated a special branch of Christianism based in the heresies of Donatus Magnus and Arius. The Donatism was spread in the Roman provinces of Numidia and Mauretania from 4th century and was a puritane version of early Christianism (previous to the Nicene Creed). The Arianism, besides it was the Christian heresy that Visigoths were adherent until king Reccared I, did not follow the Nicene Creed and the Holy Trinity. It is possible that a melting-pot Christianism with a strong Jewish influence played the same role that the Islam between the Moors in OTL. In fact, this Moorish heresy would play the national role that the Monophysite heresy played in Egypt and Syria against Constantinople.

Then, a strong army led by a good militars (as you can see, the character of Tikfarin is based on Tariq ibn Ziyad) would be conquest the major part of the Iberian Peninsula. The one difference would be the case of king Achila II. In OTL, Achila II was a Visigothic king that did not recognize king Roderic as Witiza's successor and he reigned independly in northeastern Tarraconensis (present-day Aragon and Catalonia) and Narbonesis (present-day Languedoc, in France). In this ATL, Achila II could not recover the territories conquered by the Moors, but he could resist the Moorish invasion and could be the origin of a Pyrenean nation similar to Catalan-Occitan. However, I assumed that he was defeated by the Moors as in the OTL and the whole Visigothic kingdom was conquered except the Cantabrian Mountains (Basques and Latinized tribes of Asturias and Cantabria that founded the kingdom of Asturias).Thus, the "Reconquista" would not be very different than in OTL (indeed, I put approximately intact). 

Turk invasions is another interesting issue. There were invasions from 6th century and all the major Persianates and dynasties (Ghaznavids, Ghurids, Seljukians, Khwarazmians and Safavids) were of a Turkic origin (indeed, the Azerbaijani people are descendent of them). Somewhat, the Turkic invasions in Middle East were as the Germanic invasions in Western Europe. Thus, I imagine a mixture between Turkic peoples with Persians (adherents to Mazdaism), Anatolian Greeks (adherents to the Orthodox Christianity) and Kurds (adherents to Yazidism) but also as new Turkic peoples that adapted cultural features where they started to settle (Azerbaijanis as Mazdaists). However, there is a question that I can not solve: the Turkic peoples of Crimea, Caucasus, Kazakhstan and Turkestan. I imagine the Mongol invasions as in the OTL and the Turkified khanates successors of the Mongol Empire based on nomadic Turkic peoples. I think that there are three possibilities: 

1) The Russian conquest and subsequent Russification of these nomadic Turkic peoples. Thus, they changed their Tengrianism by Russian Orthodoxy faith. It is the most plausible option. 

2A) The unification in a Turkish khanate with capital in Crimea. This Turkish Empire would follow a national religion that would have served as a unifying agent for a Turkish nation. I imagine a religious syncretism of Yazidism, Mazdaism, Manicheanism and Abrahamic religions with polytheistic Tengrist roots: Alevism (nothing to do with OTL's Alevism except the pre-Islamic Turkic influence) as a monotheistic religion with a divinity with features of the Abrahamic God and Ahura Mazda. 

2B) The influence that the Church of the East had in Turkestan would establish the Nestorian Christian faith as the main between the Turkish. It could cause that Nestorian Christianity becomes the national religion of the Turks. Thus, it could originate a Turkish Empire as in 2A or the key by the unification of the Turks through a nationalist revival in 19th century and the independence from the Russians after the February revolution. 

Well, what do you think?

I agree on alot of things but i don't think that we could compare the power of a caliphate at its full strength (in the early 8th century) to a relatively middlesized kingdom in morocco, i mean from early on we would see a balkanization of visigothic leaderships in spain, an only a few succesfull revolts in a few states would eventually bring the attention of France into the region, Even if the event of a berber intervention occurs (which isn't hard to pull it off) but its the length of time that a nation can continuously upkeep the conquest, I mean the only reason the Spanish remained with cordoba for most of the time was due to the visigothic nobles fearing the muslim represion if they attempted an uprising and that at the moment they were the biggest power in the region, and by 750, when hat changed, the Umayyads were already too prepared to mount a defense on the region and with enough troops to put down a revolt

Of course that Umayyad Caliphate was the main power on early 8th century and this empire can not compare with a Moorish empire. However, if we resort to the historical sources (in OTL) the conquest of the Iberian peninsula was made by Berbers. When Musa ibn Nusayr was called to Damascus, the Muslim conquests reached the cities of Lugo (in Galicia) and Lleida (in Catalonia). In addition, it would be possible than peripherical Visigothic nobility accepts Moorish Christianity because it is presented as a Christian branch with many similarities with Arianism, heresy that Visigoths were adherents before the Third Council of Toledo (589). The opposition should be in Catholic masses that would become in the Cartamunes (equivalent to Mozarabs in OTL).

An independent, non Islamic, Moorish Andalucía/Granada continues could be a minor power in a devided Spain.

The ATL peninsular has 7 states-

1. Portugal-
2. Andalucía-
3. Catalonia-
4. A Glaicia, Castle Leon-Asturias-Aragon royal union (ATL Spain)
5. Kingdom of Navarre 
6. Kingdom of the city of Matrit (Madrid)
7. Taifa of Toledo

Taken from- http://en.wikipedia.org/wiki/Kingdom_of_Toledo .

In April 1065 Emir Al-Muqtadir of Zaragoza besieged Barbastro, aided by 500 Sevillian knights. The governor, Count Ermengol II of Urgel, was killed in a sortie, and a few days later the city fell, whereupon the Spanish and French garrison was put to the sword, thus bringing an end to Pope Alexander II's crusade against the Moors of Spain.

At around the same time Emir Al-Muqtadir broke off relationships with Castile, and Ferdinand I lead a punitive expedition into Zaragoza - taking Alquezar - and then into Valencia. Despite being a tributary of Castile, emir Al-Mamun of Toledo lead a force in support of his son-in-law Emir Abd al-Malik. Mamun subsequently dethroned Abd al-Malik and incorporated Valencia into the Kingdom of Toledo. Ferdinand fell dangerously ill and retired from the field. Ferdinand died in December 1065, and his empire was divided between his three sons: Sancho II in Castile, Alfonso VI in León, and Garcia in Galicia.

In May 1085, after skilfully managing to pit the several Muslim kings against each other and defeating a coalition of the taifas of Seville, Badajoz and Zaragoza, Alfonso VI was able to enter the city of Toledo; the latter's taifa was incorporated with Castile and the city was made the capital of León and Castile. The former taifa lands remained subject to a long struggle with its Muslim neighbours, at least until the battle of Las Navas de Tolosa (1212).

The Muslim led Kingdom of Toledo became a subordinate Christian led southern realm of the Crown of Castille, having its own court and rulers. As the lands became more homogeneous, by the 18th century the territory was denominated New Castile, differentiating the southern area of Castile from the northern lands of Old Castile. The old Kingdom of Toledo was disestablished in 1833, and its lands compose portions of several provinces of modern Spain.