More precisely between year 0 and the rise of Islam.
Hey! I wrote about this before in a thread on What was Mohammad's religion before Islam? so I'm going to take a lot from there. Additionally, my answer will be constricted to the Arabian Peninsula itself, as that is what I know best.
Pre-Islamic Arabian Polytheism
The religions of the Arabian Peninsula pre-Islam were a mix of Christianity, Judaism, and local polytheistic beliefs (idol worship, etc). The Arabs had a pantheon of gods, and there is evidence for the names of at least 100 of them in inscriptions, poems, and other writings. Unlike some other polytheistic religions, where one god controlled a specific aspect of nature (e.g: the rain, the sun, the winds) many of the Arabian gods instead had a specific realm of focus. One village might have their gods, and then there would be gods for an entire region, and then an even larger god, for example ʿAthtar in Southern Arabia.
People would give offerings to these gods, oftentimes milk or animals, in order to appease them or appeal to them. Lower gods could also intercede with higher gods (for example supplicating your village deity to intervene with ʿAthtar). The sheer number of deities gave rise to the old Arabic proverb "When you enter a village, swear by its gods". There was nothing wrong with accepting that another village was under the "jurisdiction", if we can call it that, of different gods.
Robert Hoyland in Arabia and the Arabs: From the Bronze Age to the Coming of Islam writes about the use of votive gifts and statues as the method of worship and dedication to these gods.
Just as crucial for execution of dedications to the gods were the votive gifts themselves. Very often these were perishable items (aromatics, foodstuffs, animals etc.), but there are two types that have survived in considerable numbers. One is the stone tablet or bronze plaque, on which is inscribed a person’s dedication and usually some expression of entreaty or thanksgiving. The other is the figurine or statuette (south Arabian/Aramaic s.lm, Arabic s.anam), usually human or animal in form (Pl. 28d). They are fashioned out of a variety of different substances, most frequently stone (e.g. steatite, talc, limestone), metal (bronze, silver or gold), alabaster, wood or clay. Numerous Arabian inscriptions contain the statement that so-and-so dedicates to such-and-such a deity a statuette in the hope of obtaining/in gratitude for receiving such-and- such a blessing.
Certain towns would host these pantheons. For example, the Kaʿba in Mecca, before being turned into the object of the Islamic ḥajj pilgrimage, was a shrine hosting over 360 gods and a common pilgrimage spot. In order to facilitate the pilgrims and the tithes that they brought, the ruling tribe of Mecca, the Quraysh, even enforced a calendar system in which 4 months of the year are considered ḥarām and during which no violence in permitted.
In addition to the pantheon of gods, there were various spirits and jinn, or Genies. These jinn later got adopted into the Islamic system of belief, becoming another form of created creature akin to but more powerful than humans. According to the Islamic tradition, the Jinn were created from smokeless fire and humans from mud, and although both were created with the intent of serving God, they also had the ability to choose.
Finally, there were magicians capable of working magic and charms. One could cast spells for the weather, to cure grief, or to divine the future. Some of the practices of these soothsayers were also retained post-Islam. One example would be al-Zajr, which is described by Toufiq Fahd in La Divination Arabe (qtd. in Signs, Omens, and Semiological Regimes in Early Islamic Texts from the Harvard Center on Hellenic Studies) as:
a method of divination which essentially consisted of throwing a stone at a bird and shouting at it. A bird which flew away to right of the thrower (zājir) was taken to be a favorable portent (tafāʾala bi-hi), while the leftward-flying bird was taken as an unfavorable one (taṭayyara). Testimony for the antiquity of this practice is found in a verse of Labīd, which also indicates that al-zajr was practiced by women. [46] This is supported by a ḥadī th related by one Umm Karz, who said: “I went before the Prophet and heard him say: ‘Let the birds stay in their places’ (var. ‘in their nests’).” Asked about the meaning of this ḥadī th, al-Shāfiʿī (d. 204/820) said: “The Arabs were masters at the technique of inducing birds to fly. When one of them wished to make a journey, he would exit his dwelling until he came upon some perching birds, which he would then cause to fly away. If they flew off to the right, he would continue on his journey; but if they flew off to the left, then he would go back home.”
The difference is that while the flight of the birds would have believed to be controlled by a diety pre-Islam (in this case, Awf, although I was never able to find too much information on him), they would have been controlled by Allah after the Revelation
Pre-Islamic Arabian Monotheism
Not everyone was a polytheist though. In particular I want to highlight the existence of the ḥanīf. Being a ḥanīf essentially entailed in believing in Abrahamic monotheism (as opposed to the standard polytheism of the Arabian Peninsula at the time) but it wasn't a set religious creed. The Arabic root ḥ-n-f in ḥanīf means to incline, so ḥanīf was used in the Qurʾan to signal those who had returned to the monotheism of Abraham away from the idolatry of polytheism.
This sort of monotheism wasn't unknown. There were other figures around Muhammad's time who fell into such beliefs. One of them, the cousin of his first wife Khadija, Waraqah ibn Nawfal, was a hanīf with Christian leanings. Indeed, the fact that the Kaʿba (which became polytheistic pilgrimage center) was claimed to have been built by Abraham and his family meant that there would have been reasons for there to be ḥanīf around Mecca as a whole.
Wael Hallaq, one of the leading scholars on Islamic law, writes within his book The Origins and Evolution of Islamic Law that
Already in Mecca, Muḥammad conceived of himself as a ḥanīf, probably under the influence of a certain Zayd b. ʿAmr. Fundamentally monotheistic, ḥanīfiyya appears to have been a specifically Meccan religious development that was formed around the figure of Abraham and the Kaʿba, which he was believed to have constructed.
The ḥanīf definitely were partial to the other Abrahamic monotheistic faiths. Many of the ḥanīf ended up converting to Christianity (including Khadija's cousin Waraqah bin Nawfal) or, after the Revelation, to Islam. Zayd bin Amr was one of the few who remained fully ḥanīf, without converting to a more established religion.
Ḥanīfs as a whole were not a solifided movement, so they wouldn't have had a clergy. Certain men would preach in the countryside to those who would listen, as Muhammad would do later after the Revelation. Prior to this point, Muhammad would listen to Zayd bin Amr preach, which probably influenced the development of his own branch of monotheism.
Despite not being a solidified movement, the ḥanīfs tended to have some unifying characteristics. In an old paper, Charles Lyall wrote (by which I mean 1903, so methodology has definitely changed) about 3 of these characteristics. The Ḥanīf
all belonged to the Ḥijāz and the West of the Arabian Peninsula; (2) ... their doctrine was distinct from Christianity, although several of those who professed the Ḥanīfite faith adopted that religion, and was also distinct from Islām; and (3) ... it had certain specific features - rejection of idolatry, abstention from certain kinds of food, and the worship of "the God of Abraham"; ascetic practices, such as the wearing of sackcloth, are also ascribed to some of the Ḥanīfs (773 - 774).
The ḥanīf are not mentioned in any of the verses concerning the ʿaqd al-dhimma, or contract of protection, that was extended by Muhammad to the People of the Book. The traditional scope of the people of the book were the Jews and the Christians, the two other dominant monotheistic faiths who possessed certain customs, traditions, etc. (Although the definitions gradually expanded, with Zoroastrians, Mandeans, and controversially at times Hindus being included).
Part of this could very well be that there simply weren't many ḥanīfites, and that they were not organized enough to be considered a group worth mentioning. Charles Lyall writes that the word ḥanīf was only used by 2 poets in the time of Muhammad, and they attributed the adjective to only 10 men total (this is when ḥanīf is used to refer to a non-Islamic monotheist. The word can also be paired with the word Muslim to refer to a righteous Muslim). Of course, these are only the men important enough to be mentioned, but it holds that they were often individuals and not entire tribes who held ḥanīfite beliefs, so they wouldn't warrant the same official protections.
If you have any particular questions, please don't hesitate to ask! I understand this is more of a general overview, and rather limited to Arabia itself.
Sources
Wael Hallaq, The Origins and Evolution of Islamic Law
Ira Lapidus, A History of Islamic Societies
Richard Martin et al, Encyclopedia of Islam & the Muslim World
Robert Hoyland, Arabia and the Arabs: From the Bronze Age to the Coming of Islam
Lyall, Charles J. “The Words 'Ḥanīf' and 'Muslim'.” Journal of the Royal Asiatic Society of Great Britain and Ireland, 1903, pp. 771–784. www.jstor.org/stable/25208578.
"Signs, Omens, and Semiological Regimes in Early Islamic Texts" from the Harvard University Center for Hellenic Studies.
I cannot comment on events before 500, just as it would be unlikely for historians of the earlier period to comment on the later period, but I hope what I do know about the period from c.500-700 will nonetheless be useful.
The simple answer would be that the most popular religion from North Africa to Mesopotamia would be Christianity, but as always in history, it is a lot more complicated than that. There were in fact a multitude of different Christianities at this time, as different groups followed different teachings and readily condemned other groups as 'heretics' on occasion, yet at other times would be quite happy to co-operate. In North Africa, by which I mean the region around Carthage, around the year 500 the ruling elite were Vandal 'Arians', or more accurately Homoian Christians who got saddled with the inappropriate 'Arian' term by their enemies. By 600, the ruling Vandal elite had been vanquished by forces sent by Constantinople, so they would have been ruled by men who were uniformly Nicene Christians. Yet this didn't prevent several bishops from loudly protesting imperial religious policy in the 550s, which led to several Nicene bishops being exiled by Emperor Justinian. At the end of the century, we also hear of 'Donatism', a 'heresy' dating back to the fourth/fifth century, in North Africa, engaging in disputes with local 'orthodox' bishops. They were probably not 'real' 'Donatists', but instead a label given by Pope Gregory the Great to churchmen in North Africa who followed (what he thought were) heterodox practices - which just goes to show how describing this region as 'Christian' is not always very helpful, as internal divisions, both real and imagined, continued to play a role in their lives.
Moreover, throughout this period we can probably assume that there were people who still followed non-Christian beliefs. The evidence is slim but a Jewish minority is almost certain, as we have writings against Jews by North Africa churchmen and two examples of the province being affected by anti-Jewish edict of Emperor Heraclius in the seventh century. The same goes for paganism - we have no literary evidence of their existence by this point, but we simply cannot say that pagan beliefs did not exist in some isolated corner. What we can say however would be that paganism amongst the Moors was probably exaggerated by the literary sources, as from the archaeological and epigraphical evidence it would appear that many local Moorish leaders in the fifth and sixth centuries were following Christian practices. Later Arab traditions of a Jewish 'queen' amongst the Moors is perhaps an indicator of what some Moors believed at this point, but as the seventh century is poorly documented by contemporary sources, we cannot confirm or deny the prevalence of Judaism amongst the Moors.
The same complexities and ambiguities were applicable in the Middle East. Syria, Palestine, and Egypt were for instance mired in the divisions between Chalcedonianism and miaphyisitism, both forms of Nicene Christianity but which differed on their views of the Council of Chalcedon in 451. I described their history in some detail in this comment, pointing out both instances of conflict and co-operation. Beyond Christianity, we know for certain of large communities of Jews and Samaritans in Palestine, which should not be a surprise.
Mesopotamia, by which I mean essentially modern-day Iraq but back then only one part of the empire ruled by the Sassanian Persians, is another interesting example, as the ruling elite followed Zoroastrianism, but a majority of the population as a whole was Christian - they were however 'Nestorian' Christians, or more accurately East Syrian Christians, who split with the Nicene Church in the west over the Council of Ephesus in 431. Again there were significant divisions with other churches, but also instances of co-operation - the Chalcedonian patriarch of Antioch for example went to Mesopotamia and consecrated churches dedicated to the Virgin Mary at the end of the sixth century, a very understandable action when the Virgin Mary in late antiquity was an ecumenical figure that cut across religious divides. Their relationship with the Zoroastrian ruling class was similarly changeable - there were bout of persecutions, but Christians had also mingled with their rulers. In the case of Khusro II (590-628), the last great Sassanian ruler, he even actively favoured certain Christian groups (miaphysites and East Syrian Christians - the Chalcedonians were too closely aligned with Constantinople), even to the extent of persecuting Jews in Jerusalem when he conquered the city in 614. His policies no doubt contributed to the rumour that he had personally converted to Christianity, itself an indication of the religious flexibility evident in this period.
Arabia itself was similarly divided. Pagan polytheist beliefs persisted, but we also have literary evidence of a Jewish kingdom in Yemen in the early sixth century, which coincidentally was destroyed by an army from Christian Ethiopia, which led to the creation of an independent kingdom ruled by a rebellious Ethiopian general. In the seventh century, we also have contemporary Jewish inscriptions and Jewish poets (based on what is transmitted in much later collections), both topics that have been recently examined by Robert Hoyland. Christianity also played a role; aside from the Ethiopian intervention, which was seemingly the result of Jewish persecution of Christians and a call for help that also reached Constantinople and Ctesiphon, powerful Christian Arab chiefs were also dominant in the borderlands of Arabia. The Jafnid leadership of the Ghassanid confederation for instance were firm adherents of miaphysite Christianity and repeatedly got involved in church disputes in Syria. The Nasrid elite at the head of the Persian-aligned Lakhmid confederation on the other hand remained pagan until the end of the sixth century, yet they also ruled over Hira, a city filled with East Syrian Christians. The last Nasrid leader did convert to Christianity in the end, yet his conversion to East Syrian Christianity also netted him praise from Evagrius, a Chalcedonian churchman in Syria.
In more ways than one then, a look at the Arab leaders of this period actually confirms the patterns I identified above. There were notable divisions, but that did not prevent individuals from crossing the borders between different religious communities. The religious situation in North Africa and the Middle East was complex, so Islam was just another belief that had to navigate this complicated world. If we follow some of the more revisionist narratives, then Islam itself was fundamentally inclusive of Christian and Jewish beliefs (most prominently the interpretations of Fred Donner and the late Patricia Crone). It was a religion forged in Arabia, a seemingly isolated part of the world of late antiquity, but it was nonetheless plugged into developments elsewhere. To explain this, I can do no better than to quote Peter Sarris from his Empires of Faith: The Fall of Rome to the Rise of Islam, 500-700 (2011):
The religion of Muhammad as it emerges from the earliest sources was a faith deeply engaged with wider debates and concerns that were coming to dominate the religious life of the Mediterranean world into which Arabia, from the fringes of Syria to the Yemeni littoral, was increasingly being drawn. The verses of the Qur’an reveal a preoccupation with the imminence of the apocalypse, and a determination to counter those who denied the existence of the afterlife, such as we have already encountered in the writings of Pope Gregory the Great. Like Gregory’s Book of Pastoral Care (or the Spiritual Meadow of the seventh-century Palestinian monk John Moschus, who wrote under papal patronage), its verses offer an intensified but pragmatic piety whereby the core asceticism of the ‘Holy Man’ was available to all. The vision of paradise contained in the work, and the rituals associated with prayer that we encounter in early Islam, moreover, bear a striking resemblance to those found in the early Christian Syriac ascetic tradition. The respect in the Qur’an for the Virgin Mary, but its denial of Jesus’ divinity and crucifixion, chime closely with shades of contemporary Christianity, both ‘orthodox’ and ‘heterodox’. Indeed, it is striking that a Christian heresy is precisely what the eighth-century Syrian theologian John of Damascus regarded Islam to be. What Muhammad’s austere monotheism cut through were the complexities and controversies of Christian Trinitarian and Christological doctrine. In that sense it was itself a fulsome response to contemporary Christian debate.
[...]
That Muhammad should have preached a doctrine of martyrdom and holy war at precisely the time that these selfsame concepts were featuring so prominently in the official pronouncements of the East Roman state is highly suggestive, and may indicate that Heraclian propaganda was percolating into the Arabian peninsula. The region around Mecca appears to have been one of the few parts of Arabia that had not come under direct Persian control by the late sixth and early seventh centuries, and thus it may have been something of a bastion of pro-Roman sentiment. Certainly, sympathy for Heraclius’ cause is strongly indicated by the Qur’anic verse on ‘the Greeks’ (al-Rum), possibly recording the Persian defeat of Roman forces near Bostra in 613.
Viewed from this perspective, the Arab conquests and the rise of Islam did not signal the end of the world of late antiquity - instead, the rise of a new monotheist religion was instead another development, which both grew out of and was in reaction against the trends I outlined here.
As an aside, how long did it take for Islam to displace local religions (and Christianity, I suppose) in the areas following the Muslim conquest? Did syncretic beliefs remain for long?