During antiquity the city of Medina was known as Yathrib (يثرب). In historiography, the term "Yathrib" or "ancient yathrib" describes the periods of occupation starting with early Arab-Jewish settlements in the area during the fourth or fifth century CE. Though it is uncertain how far back the settlement history of Yathrib Oasis goes, it is believed that the area was inhabited at least for over 1,500-1,700 years (circa 900-700 BCE) before prophet Muhammad's migration from Mecca. The Yathrib region received peoples from various regions who formed its pre-Islamic community and fomulate history.

circa 1700 BCE to 600 CE

According to some historians (mostly from the early eighth century CE), the first people to inhabit the land of Yathrib were the Su'l and Falij, who fought Propht Dawood (biblical king David) and lost. These people were wiped because of a mysterious "worm". Su'l and Falij were followed by the Amalekites (a people well known from Biblical history). Prophet Moses sent an army towards them to destroy the Amalekites in the Hejaz region. They were instructed to kill all of the Amalekites but they disobeyed Moses' instructions and did not kill one handsome individual, said to be the son of the king. These were said to be the first Jews to inhabit the ancient land of Yathrib (though they did settle in other parts of the Arabian Peninsula).

The earliest Jewish people are believed to have migrated to Arabian Peninsula as early as the late sixth century BCE (after the collapse of Kingdom of Judah, that was destroyed by Nebuchadnezzar, king of Babylon, in 586 BCE). In Islamic tradition, the Jewish tribes of the Hejaz were seen as the offspring of the ancient Hebrews who had migrated to the Yathrib in waves over the centuries. Another major wave of Jewish migration towards the Arabian Peninsula happened after the Roman destruction of Jerusalem in 70 CE.

It is quite certain that by the early or mid third century CE, Arab tribes (most likely the ancestors of 'Aws and Khajazrj) migrated from Yemen (Sabaean Kingdom), began to settle in the Yathrib Oasis. This migration happened sometime around the destruction of the Ma'rib Dam in ancient Saba. These were the earliest Arab people to migrate to the ancient city of Yathrib in the recorded history of Hejaz.

Around the closing of the fifth century CE, there was a shift in power in Yathrib as the Jewish leaders lost control of the city to two Arab tribes 'Aws and Khazarj. The balance of power shifted as the Arab tribes of Banu 'Aus and Banu Khazraj gained dominance in Medina with external support and executing a massacre of prominent Jews during a banquet. Though the Jewish tribes became clients of the 'Aws and Khazarj Arab tribs, a measure of political independence still remained with them.

By the early to mid sixth century CE there were two notable Arab tribes 'Aws and Khazarj and three Jewish tribes, the Banu Qaynuqa, the Banu Qurayza, and Banu Nadir, that inhabited the city around the time of prophet Muhammad.

Over the next few decades (during the sixth century CE) the dynamics shifted again and Banu 'Aws and the Banu Khazraj became hostile to each other. By the time of prophet Muhammad's Hijrah (emigration) to Yathrib Oasis in 622 CE, they had been fighting for 120 years and were sworn enemies. The Jewish tribes of Banu Nadir and the Banu Qurayza were allied with the 'Aws, while the Banu Qaynuqa sided with the Khazraj. These tribes had fought a number of battles as well.

A few years before the arrival of prophet Muhammad in Yathrib, Battle of Bu'ath, bloodiest and last of the battles was fought in 617/618 CE. The outcome of the battle was inconclusive, and the feud continued. It was a time of uncertain politics without a hegemon. Consequently, to address this issue, a chieftain from the Khazarj tribe, 'Abd Allah ibn Ubayy, was named to become the chief of Yathrib to mediate and stop the ongoing bloodshed, but the plan did not materialize as it was around the same time 618/619 CE when the news reached Yathrib of a prophet in Mecca.

Two delegations from the 'Aws and Khajazrj tribes met prophet Muhammad outside Mecca to invite him as a mediator among them to the city of Yathrib. These two delegations (first in the 11th and second in the 13th year of Nabawi) are known as the "Pledges of 'Aqabah" in Islamic History and are precursors to a turning point not only in the political landscape of oasis city of Yathrib but the whole of Arabian Peninsula.