Jewish tribes of Arabia
The Jewish tribes of Arabia were ethnic groups professing the Jewish faith that inhabited the Arabian Peninsula before and during the advent of Islam. In Islamic tradition, the Jewish tribes of the Hejaz were seen as the offspring of the ancient Hebrews. The Jewish tribes 
Some of the Jewish tribes of Arabia historically attested include:

Banu Harith or Bnei Chorath
Banu Qaynuqa 
Banu Shutayba
Jafna Clan of the Banu Tha'laba who were exiled members of the Banu Ghassan - while both tribes were not Jewish, they did have Jewish members; whereas the Jafna Clan was solely Jewish 
Banu Zaura
Banu Zurayq In Islamic lore, Labid ben Asam was a Jewish sorcerer who cast a spell on Muhammad that made him ill for several months and prevented him from having sexual relations with his wives
Banu Quda'a — Himyarite tribe of converts to Judaism
Banu Qurayza — sub-clan of the al-Kāhinān, located in Yathrib (Medina)
Banu Nadir — sub-clan of the al-Kāhinān, located in Yathrib (Medina)
Banu Juw — sub-clan of the Banu Qaynuqa, fled to North Africa. Banu Aws
Banu Awf

History of immigration
Judaism found its place in the Arabian Peninsula by immigration of Jews, which took place mainly during six periods:

 After the collapse of Kingdom of Judah in 586 BCE. After the Roman conquest of Judea. After the Jewish rebellion in 66 CE, and the destruction of Jerusalem by Titus in 70 CE, exiles found a home in the desert. Survivors of the Bar Kochba Revolt, in 135 CE, who sought religious freedom in the Arabian desert rather than live under the yoke of the Romans. Immigration, around 300 CE, by people who are known in Islamic literature as the Banu Aus and the Banu Khazraj who fled the Ghassanids in Syria. Migration from Judea into southern Arabian Peninsula to ride the ascent of the Himyarite Kingdom around 380 CE. Sanaite
The Sanaite Jews have a tradition that their ancestors settled in Yemen forty-two years before the destruction of the First Temple. According to Jeremiah some 75,000 Jews, including priests and Levites, traveled to Yemen. The Banu Habban in southern Yemen have a tradition that they are the descendants of Judeans who settled in the area before the destruction of the Second Temple. These Judeans supposedly belonged to a brigade dispatched by King Herod to assist the Roman legions fighting in the region. The Himyarite royal family in exile commanded vast wealth and resources, particularly the Nabatean bedouin with whom they had controlled the market of trade by Land from North-East Africa for centuries. By the close of the fifth century, the Banu Aus and Banu Khazraj had become masters of Yathrib. During these events, or possibly in coordination with them, Yathrib was host to a noble visitor. In 470 CE, Persian King Firuz was attempting to wipe out the Exilarchate. The Exilarch Huna V, who was the son of Mar-Zutra bar Mar-Zutra, whisked his daughter and some of his entourage to Yathrib (Medina) for safety. Judaized Arabs and the Himyarite Kingdom
In about 400 CE, Himyarite King tubba Abu Karib As'ad Kamil (385-420 CE), a convert to Judaism, led military expeditions into central Arabia and expanded his empire to encompass most of the Arabian Peninsula. His army had marched north to battle the Aksumites who had been fighting for control of Yemen for a hundred years. The Aksumites were only expelled from the region when the newly-Jewish king rallied Jews together from all over Arabia with pagan allies. The relationship between the Himyarite Kings and the polytheistic Arab tribes strengthened when, under the royal permission of Tubba' Abu Karib As'ad, Qusai ibn Kilab (400–480 CE) reconstructed the Ka'aba from a state of decay, and had the Arab al-Kahinan (Cohanim) build their houses around it. Qusai ibn Kilab was the great-great- grandfather of Shaiba ibn Hashim (Abdul-Mutallib). Shaiba ibn Hashim was fifth in the line of descent to Muhammad, and attained supreme power at Mecca. Qusai ibn Kilab is among the ancestors of Sahaba and the progenitor of the Banu Quraish. When Qusai came of age, a man from the tribe of Banu Khuza'a named Hulail (Hillel) was the trustee of the Kaaba, and the Na'sa (Nasi)—authorized to calculate the calendar. Qusai married his daughter and, according to Hulail's will, obtained Hulail's rights to the Ka'aba. Hulail, according to Arabian tradition was a member of the Banu Jurhum. Banu Jurhum was a sub-group of the Banu Qahtani from whom the Himyarites originally descend. Around 455 CE, the last Himyarite King is born, Zur'ah Yusuf Ibn Tuban As'ad Abu Kaleb Dhu Nuwas or Dhu Nuwas. He died in 510. His zeal for Judaism brought about his fall. Having heard of the persecutions of Jews by Byzantine emperors, Dhu Nuwas retaliated by putting to death some Byzantine merchants who were traveling on business through Himyara. He didn't simply kill them with hanging—he burned them in large pits—earning him the title "King of the burning pit". These killings destroyed the trade of Yemen with Europe and involved Dhu Nuwas in a war with the heathen King Aidug, whose commercial interests were injured by these killings. Dhu Nuwas was defeated, then he made war against the Christian city Najran in Yemen, which was a dependency of his kingdom. After its surrender, he offered the citizens the alternative of embracing Judaism, under coercion, or being put to death. As they refused to renounce their faith, he executed their chief, Harith ibn Kaleb, and three hundred and forty chosen men. Rise of Islam

The Jewish tribes played a significant role during the rise of Islam. Muhammad had many contacts with Jewish tribes, both urban and nomadic. The eating of pork has always been strongly prohibited in both religions. In the Constitution of Medina, Jews were given equality to Muslims in exchange for political loyalty and were allowed to practice their own culture and religion. A significant narrative symbolising the inter-faith harmony between early Muslims and Jews is that of the Rabbi Mukhayriq. The Rabbi was from Banu Nadir and fought alongside Muslims at the Battle of Uhud and bequeathed his entire wealth to Muhammad in the case of his death. He was subsequently called ″the best of the Jews″ by Muhammad. Later, as Muhammad encountered opposition from the Jews, Muslims began to adopt a more negative view on the Jews, seeing them as something of a fifth column. Early Muslim conquests resulted in the exile of the Banu Qainuqa and Banu Nadir, two of the main three Jewish tribes from Medina, and the mass execution of all male adults of the Banu Qurayza clan. Some historians, like Guillaume, sees the attacks on the Banu Qaynuqa for their hosilitlty against the Muslims and for mocking them. They left for modern-day Der'a in Syria. In one account, the Banu Nadir tribe was evicted from Medina after they attempted to assassinate Muhammad. See also
Arabian tribes that interacted with Muhammad
History of the Jews in the Arabian Peninsula
Yemenite Jews
Mizrahi Jews
Arab Jews
Dhu Nuwas
Moses Maimonides
Banu Israil

References

Bibliography

 
History of the Jews in the Arabian Peninsula
Arab people of Jewish descent