During antiquity the modern 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.

Samhoudi relates from abu al-Qasim Zajjaji, that the first person to arrive in the area was known as Yathirb bin Qayina bin Mahlail bin Iram bin Ubail bin Aus bin Iram bin Sam bin Nuh.

circa 1700 BCE to 600 CE

According to some early Islamic-era traditions, the Amalekites were the first people to settle in the land of Yathrib. Known from Biblical accounts as fierce and ancient adversaries of the Israelites, the Amalekites are described in later Islamic narratives as having inhabited the Hejaz region, including the area around Yathrib. In one tradition, Prophet Moses (traditionally dated to the 13th or 15th century BCE) sent an army against the Amalekites in this region with orders to annihilate them completely. The army, however, reportedly disobeyed his instructions by sparing one individual—a handsome young man said to be the son of the Amalekite king. According to this version of events, the descendants of that survivor were among the earliest Jewish inhabitants of Yathrib, predating the major known waves of Jewish migration to the Arabian Peninsula following the Babylonian destruction of Judah in 587 BCE and the Roman destruction of Jerusalem in 70 CE. While there is no archaeological or textual evidence to support the presence of Amalekites in Yathrib specifically, these stories reflect early Muslim attempts to frame Yathrib's antiquity within a Biblical and prophetic context.

However, another set of traditions—also preserved from the eighth-century Islamic historiography—names Su'l and Falij as the first people to inhabit the Yathrib region. In these accounts, Su'l and Falij are said to have fought Prophet Dawood (King David, who reigned circa 1000–960 BCE) and lost. Their destruction, according to this narrative, came not merely through battle but by a mysterious "worm"—a symbolic element that suggests mythic or allegorical dimensions. Like the Amalekite tradition, there is no independent historical or archaeological attestation for Su'l and Falij. Nonetheless, the persistence of these names in the collective memory of early Muslim historians indicates either an effort to construct a multi-layered pre-Islamic history of Yathrib—linking it to prophetic figures and ancient regional power struggles—or the faint preservation of events from a time long gone, whose traces have not survived in the historical or archaeological record but may well have taken place.

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.