The ancient ruins of Beisan
, Raja's hometown
Raja, known also by his kunya "Abūʾl-Miqdām" or "Abū Naṣr", was the son of a certain Haywa ibn Khanzal. He was born in Beisan (Beit She'an) in the Jordan district before moving south to Palestine. According to a report traced to Raja and recorded by the medieval Egyptian historian al-Suyuti (d. 1505), Raja ultimately considered himself a Jerusalemite. His approximate year of birth was c. 660, during the early reign of the first Umayyad caliph, Mu'awiya I (r. 661–680).
The 9th-century historian Khalifa ibn Khayyat mentions that Raja was a mawlā (non-Arab, Muslim client or freedman) of the Kinda. Because of his family's residence in the Palestine or Jordan district of Syria, Raja is occasionally given the nisba (epithet) of al-Filasṭīnī ("the Palestinian") or al-Urdunnī ("the Jordanian"). The family likely hailed from or settled in an area inhabited by their Kindite tribal patrons, whose prominence in Syria had grown under Mu'awiya and further still under Caliph Marwan I (r. 684–685).