Sa panahon ng Byzantine (simula 390 CE), ang rehiyon na dating bahagi ng Imperyo ng Roma ay naging dominado ng Kristiyanismo sa ilalim ng pamamahala ng Byzantine. Ang pagbabagong ito ay pinabilis ng pagdagsa ng mga Kristiyanong peregrino at ang pagtatayo ng mga simbahan sa mga lugar ng Bibliya.^[123] Ginampanan din ng mga monghe ang pagpapalit ng mga lokal na pagano sa pamamagitan ng pagtatayo ng mga monasteryo malapit sa kanilang mga pamayanan.^[124]Ang pamayanan ng mga Hudyo sa Palestine ay nahaharap sa paghina, na nawala ang katayuan ng mayorya noong ikaapat na siglo.^[125] Ang mga paghihigpit sa mga Hudyo ay tumaas, kabilang ang mga pagbabawal sa pagtatayo ng mga bagong lugar ng pagsamba, paghawak ng pampublikong tungkulin, at pagmamay-ari ng mga aliping Kristiyano.^[126] Ang pamunuan ng mga Hudyo, kabilang ang tanggapan ng Nasi at ang Sanhedrin, ay binuwag noong 425, kung saan ang sentro ng Hudyo sa Babylonia ay sumikat pagkatapos noon.^[123]Ang ika-5 at ika-6 na siglo ay nakita ang mga pag-aalsa ng Samaritan laban sa pamamahala ng Byzantine, na pinigilan, pinaliit ang impluwensya ng Samaritano at pinalalakas ang dominasyong Kristiyano.^[127] Ang mga talaan ng mga Hudyo at Samaritana na pagbabalik-loob sa Kristiyanismo sa panahong ito ay limitado at karamihan ay tumutukoy sa mga indibidwal sa halip na mga komunidad.^[128]Noong 611, si Khosrow II ng Sassanid Persia , na tinulungan ng mga pwersang Hudyo, ay sumalakay at nakuha ang Jerusalem.^[129] Kasama sa paghuli ang pag-agaw sa "Tunay na Krus".Si Nehemias ben Hushiel ay hinirang na gobernador ng Jerusalem.Noong 628, pagkatapos ng isang kasunduan sa kapayapaan sa mga Byzantine, ibinalik ni Kavad II ang Palestine at ang Tunay na Krus sa mga Byzantine.Ito ay humantong sa isang masaker sa mga Hudyo sa Galilea at Jerusalem ni Heraclius , na muling ipinagbawal ang pagpasok ng mga Hudyo sa Jerusalem.^[130]