Ennek az lehet az oka, hogy akik az Arábiai félszigeten megtelepedtek, elkerültek és el is szigetelődtek népük többi csoportjától, végül a világ többi helyén élő Zsidó közösségek megfeledkeztek róluk és nem tartották számon őket. Ráadásul felhagytak Zsidó kultúrájuk művelésével, nem beszéltek Héber nyelven, még neveik is elarabosodtak. A régészeti feltárásokon előkerült agyagtáblákon Hedzsazban (a Vörös tengerrel szomszédos régió) nincs nyoma ez első évszázad előtti Zsidó jelenlétnek, eltekintve néhány Zsidó névtől. Ezért az itteni Zsidóság történetét az a szájhagyomány adja, amit azok a kortárs Arabok tartottak fenn, akik velük egy közösségben éltek.
A Hedzsazi Zsidók úgy tartják, hogy ők Mózes Próféta életének végső szakaszában kerültek oda. Azt állítják, hogy Mózes egy sereget küldött, hogy elűzzék Yathribból (ma Medina) az Amalekitákat, elrendelve azt, hogy egy élő lelket sem hagyhatnak meg közülük. Az Izraelita sereg végrehajtotta a parancsot, de egy nemes Amalekita herceg életét meghagyták, akivel visszatértek Palesztinába. Ekkorra Mózes már meghalt, utódja fogadta a visszatérő hadat, de látva az Amalekita herceget, a katonákat a Mózesi törvény megsértésével vádolták. Ennek következtében ők megváltak a seregtől, közösségüktől, majd visszatértek Yathribba és végleg ott telepedtek le. (Kitab al-Aghani, vol. XIX. p. 94). A Zsidók szerint, így ők az i. e. 1200 óta Yathribban élnek.
A második Zsidó migráció a Zsidók emlékezete szerint az i. e. 587-ben következett be, amikor Babilon királya, Nebukadnezár lerombolta Jeruzsálemet és szétszórta a Zsidókat a világba. Több Arab Zsidó nemzetség ekkor érkezett Wadi al-Qura, Taima és Yathrib helységekbe. (Al-Baladuri, Futuh alBuldan).
Történelmileg igazolható, hogy miután 70-ben a Rómaiak lemészárolták a Zsidókat Jeruzsálemben, lerombolták a Templomot, majd 132-ben, aki még maradt, elűzték onnan, sok Zsidó nemzetség menekült Hedzsazba, ami gyakorlatilag Palesztina déli területeinek folytatása volt. Ahol vízforrásra, zöldre leltek, letelepedtek és munkával, az üzleti életbe való bekapcsolódással, fokozatosan integrálódtak a helyi környezetbe. Így épült ki Ailah, Maqna, Tabuk, Wadi al Qura, Bani Bahdal és Bani Qainuqa, valamint ebben az időben jöttek nagy számban Yathribba is.
A Yathribban megtelepedő nemzetségek közt kapott helyet Bani al Nadir és Bani Quraizah, akik Koheniták voltak, tehát előkelő, papi leszármazással büszkélkedhettek, ezért a többi Zsidó feletti vallási vezetést a kezükbe ragadták. Amikor Yathrebbe érkeztek, ott már éltek emberek, akiket legyőztek és gyakorlatilag a zöld és termékeny területek gazdái lettek.

I.e. 115- i.sz. 330 közötti időszakban a mai Jemen területén Himyarita királyság uralkodott. Uralkodóik elfoglalták Sábát, Qatabánt és a fővárost Maarebből Zafarba helyezték át. Zafar mezőgazdaságilag fejlett kultúrát hozott létre és élénk kereskedelmet bonyolított egészen a 3. századig, amikor a Nabateusok átvették a dominanciát a Hidzsazi régió felett. Ennek, valamint a belső hatalmi harcaiknak következtében a Himyar dinasztia családjai szétszóródtak az Arab félsziget egész területén, de magukkal vitték kultúrájukat és hitvilágukat.

A Himyarita királyok elvetették a politeizmust és 380 körül áttértek a Judaizmusra. Ez néhány dekáddal azt követően történt, ahogy az Akszumi etióp királyok keresztény hitre tértek (340). Az első zsidó hitre betért uralkodók közé tartozott Tubaa Abu Kariba Assad (390-420), aki több hadjáratot vezetett a bizánci befolyás megtörésére északon, ill. a kereszténnyé és bizánci szövetségessé lett nyugati akszumi előretörés megfékezésére nyugaton. Próbálkozásai nem jártak sok sikerrel. Tubaa Abu Kariba betérését két yathrebi zsidó tudós érte el. A kor szokása szerint a király betérését követően a népnek is fel kellett venni a judaizmust. Ettől kezdve az Arab félsziget multikulturálissá vált, hiszen a Jemen északi területén, Nadzsranban élő arabok között terjedt a kereszténység, amit az akszumi abesszin uralkodók erősen támogattak, valamint a sokszínű bálványimádás mellett a judaizmus is gyökeret vert. Ez utóbbinak két jól elkülöníthető formája a Zsidó diaszpóra megtelepedése, valamint az arabok Judaizmusra térése volt.

450-451-ben bekövetkezett a Maarebi gát szakadása Jemenben és a katasztrófa következtében Sába népei elvándorlásra kényszerültek. Ennek következményeként Bani Ghassan a mai Szíria, Bani Lakm a mai Irak területén, Bani Khuzaa Dzsidda és Mekka között, Awasz és Khazradzs pedig Yathribban telepedtek meg. Mivel Yathrib felett Zsidók uralkodtak, akik először nem engedték be az Awasz és Khazradzs nemzetséget a termelésbe vett területekre, ezért ők a terméktelen, nehezen művelhető régiókban eresztettek gyökeret, ahol nehézkesen tudtak megélni. Végül egyik főnökük elment Szíriába, hogy segítséget kérjen a Bani Ghassanhoz tartozó testvéreitől, akik sereget küldtek és ezzel megtörték a Zsidók uralmát. Az Awasz és Khazradzs felügyelete alá vette Yathrebet, a két nagy Zsidó nemzetség, a Bani an-Nadir és Bani Quraizah a városon kívül eső negyedbe szorult. A harmadik nemzetség, a Bani Qainuqa nem élt barátságban a két másik Zsidó törzzsel, ők a városon belül telepedhettek meg, és ahogy akkor szokás volt, a Khazradzsokat kérték fel oltalmazójukul. Ennek válaszreakciójaként pedig Bani al Nadir és Bani Quraizah az Awaszokhoz fordult oltalomért.
Mohamed próféta Medinába való érkezése előtt a Hedzsazi és ezen belül különös tekintettel a Medinai Zsidók pozíciójára a következők voltak jellemzők:

1. Nyelv, viselet, kultúra és életmód tekintetében teljesen elarabosodtak, még neveik is Arab nevek voltak. A Hedzsazban megtelepedett 12 Zsidó nemzetség közül csak a Bani Zuara őrizte meg a Héber neveket. Csak pár hittudós tudott Héberül. Nincs nyoma az Iszlám előtti korban az Arabtól elkülönülő kultúrának, ami megnyilvánult volna költészetben, vagy más formában. A Zsidó- Arab vegyes házasság teljesen normális volt. A vallási hagyományokon kívül más különbség nem volt köztük és az Arabok között. A túlélés miatt a felszínen Arabnak mutatkoztak, amire rákényszerültek Arábiában, de ezzel együtt nem vesztették el identitástudatukat.
2. Elarabosodásuk miatt a nyugati orientalisták egy része nem is tartja őket ténylegesen Izraelitáknak, hanem Araboknak, akik magukévá tették a Judaizmust, vagy legalábbis többségükben Arabok, akik Zsidók lettek. Nincs semmi bizonyíték arra, hogy a Zsidók Hedzsazban térítő tevékenységgel foglalkoztak volna, vagy a rabbik valaha is Arabokat hívtak volna a Judaizmusra, ahogy a Keresztény papok és misszionáriusok tették. Ezzel ellentétben, inkább büszkék voltak Izraelita származásukra. Az Arabokat pogányoknak tartották, így vallási szempontból megkülönböztették őket. Az Arab főembereken kívül nem tartották magukat a közemberekkel egyenlő szinten még akkor sem, ha az illető betért a Judaizmusba. Arra nincs történelmi bizonyíték, hogy egy Arab klán egésze, vagy egész törzs Hedzsazban betért volna a Judaizmusba, de ugyanez egyének szintjén sokszor előfordult. A Zsidókat jobban lekötötte a kereskedelem, mint vallásuk hirdetése, ezért a Judaizmus nem terjedt Hedzsazban vallásként, inkább a büszkeség jele és megkülönböztető tényező maradt a helyiek között. A Zsidó rabbik ugyanakkor virágzó üzletet tartottak fenn amulettek, szerencsét hozó tárgyak, bájitalok, stb. árulásából, az Arabok megítélésében hozzájuk kötődő efféle jártasság és „tudás” miatt.
3. Gazdaságilag sokkal erősebbek voltak az Araboknál. Mivel olyan országokból kényszerültek el (Palesztina, Szíria), ahol civilizációk, kultúrák virágoztak, onnan ideérkezve kulturális fölényben voltak a helyiekkel szemben. Olyan művészetekhez értettek, melyekről az Arabok nem is hallottak. Ugyanakkor kereskedelmi szálaik nem szűntek meg egykori anyaországaikkal és a külvilág más részével is élénk kapcsolatot ápoltak. Kezükben volt a Hidzsazba és Yathribba irányuló gabonaimport, valamint onnan a szárított datolya export. Emellett kereskedtek halakkal, baromfival, de híres volt vászonszövésük, ruhagyártásuk is. Bort importáltak Szíriából és borelosztó hálózatot tartottak fenn. A Bani Qainuqa arannyal kereskedett, de jó kovácsaik és hajóácsaik is voltak. Mindemellett a Zsidók hatalmas vagyonra tettek szert a pénzkölcsönzésből származó profitjaikból. Az Arabok, főleg az elöljárók fellengzős kivagyiságát, pompáját, erőfitogtatását jól kihasználták, mert ehhez az Arabok sok kölcsönt vettek fel tőlük, amire rájött a kamat és sok esetben a kamatos kamat, ami megalapozta hosszútávon azt, hogy sokan eladósodtak nekik. Mindez sok haragot és ellenszenvet szült. 
4. Abban sem voltak érdekeltek, hogy nagy barátság alakuljon ki Arab törzsek között, de abban sem, hogy ezek háborúskodjanak egymással. Mivel hatalmas kertjeik, palotáik, birtokaik voltak, melyeket a pénzkölcsönzésből szereztek, tartottak attól, hogy egy nagy Arab egység esetén ezekre ráteszik a kezüket. Akkor az volt szokásban, hogy nem élhettek a törzsek szövetséges nélkül, aki megvédi őket. Ezért mindegyik Zsidó törzs felett egy erős Arab szövetséges őrködött. Ez azt is jelentette, hogy amikor az adott Arab oltalmazó egy másik Arab törzzsel háborúba keveredett, akkor a Zsidóknak katonákat kellett adniuk szövetségeseik seregébe. Ha az ellenség soraiban is voltak azokkal szövetséges Zsidók, akkor arra kényszerültek, hogy egymás ellen harcoljanak, ami önmagukon belül sok feszültséghez vezetett. Yathribban a Bani Quraizah és Bani an-Nadir oltalmazója az Awasz, míg a Bani Qainuqa szövetségese a Khazradzs törzs volt. Kevéssel Mohamed próféta Medinába érkezése előtt a két Arab törzs összeütközésbe (Buathi ütközet) keveredett egymással, ami kihatott a Zsidó törzsek egymás közti kapcsolatára.