The existence of a Christian community in Najran is attested by several historical sources of the Arabian peninsula, where it recorded as having been created in the 5th century CE or perhaps a century earlier. According to the Arab Muslim historian, Ibn Ishaq, Najran was the first place where Christianity took root in South Arabia.
Prior to the rise of Christianity, the people of Najran were polytheists and worshipped a tall date-palm tree, for which also they had an annual festival when they hung upon it the finest garments they could find, and female ornaments. Then they would come and dance around it the whole day. During this period, they had a Chief named Abdullah ibn ath-Thamir who became the first Najranite to embrace Christianity. A pious Christian builder and bricklayer named Phemion settled among them and led them to his religion and its religious laws, which they adopted.
Before the advent of Islam, it appears from indications in the Qur'an it would appear that the Jews to the West of the Himyarite kingdom, in western Arabia, maintained some form of rabbinical organisation, possibly connected to late antique Judaism, and were not wholly cut off from their brethren elsewhere in the Middle East. On source speaks of rabbis from Tiberias itself enjoying the hospitality of Dhu Nuwas's court. The apparent conversion of local Himyarite rulers to Judaism, or some form of a Judaic monotheism, as early as the late fourth century under the Tabbāi'a dynasty, is indirect evidence that suggests appear to have been effective Jewish proselytization was active in the region.
The Christians of Najran were divided into two sects. One drew on a variety of Nestorianism, which a local merchant had acquired during a sojourn in al-Hira, and took back to Najran sometime during the reign of the Sassanid ruler Yazdegerd II. The other was a form of anti-Chalcedonianism. had suffered an earlier, but brief, stint of persecution with the advent of the new dynasty under the Himyarite ruler Shurihbi'īl Yakkuf (c.468-480). The Jewish faith had strong roots within the Himyarite kingdom when Dhu Nuwas rose to power, and not only in Zafar but Najran also, it seems that several synagogues had been built.