Bysantin aikana (alkaen vuodesta 390 jKr.) Rooman valtakuntaan kuulunutta aluetta hallitsi Bysantin vallan alainen kristinusko . Tätä muutosta kiihdyttivät kristittyjen pyhiinvaeltajien tulva ja kirkkojen rakentaminen raamatullisiin paikkoihin.^[123] Munkeilla oli myös rooli paikallisten pakanoiden käännyttämisessä perustamalla luostareita lähelle heidän asutustaan.^[124]Palestiinan juutalainen yhteisö joutui taantumaan ja menetti enemmistön asemansa neljännellä vuosisadalla.^[125] Juutalaisiin kohdistuvat rajoitukset lisääntyivät, mukaan lukien kiellot rakentaa uusia palvontapaikkoja, hoitaa julkisia virkoja ja omistaa kristittyjä orjia.^[126] Juutalainen johto, mukaan lukien Nasin toimisto ja sanhedrin, hajotettiin vuonna 425, ja Babylonian juutalaiskeskus nousi sen jälkeen näkyvämmäksi.^[123]5. ja 6. vuosisadalla samarialaiset kapinoivat Bysantin valtaa vastaan, ja ne tukahdutettiin, mikä vähensi samarialaisten vaikutusvaltaa ja vahvisti kristityn valta-asemaa.^[127] Tiedot juutalaisten ja samarialaisten kääntymyksestä kristinuskoon tänä aikana ovat rajallisia ja koskevat enimmäkseen yksilöitä eikä yhteisöjä.^[128]Vuonna 611 Sassanidi - Persialainen Khosrow II hyökkäsi juutalaisten joukkojen avustuksella Jerusalemiin ja valloitti sen.^[129] Sieppaukseen sisältyi "True Crossin" takavarikointi.Nehemia ben Hushiel nimitettiin Jerusalemin maaherraksi.Vuonna 628, kun rauhansopimus oli tehty bysanttilaisten kanssa, Kavad II palautti Palestiinan ja todellisen ristin bysanttilaisille.Tämä johti juutalaisten verilöylyyn Galileassa ja Jerusalemissa Herakleioksen toimesta, joka myös uudisti juutalaisten pääsyn Jerusalemiin kiellon.^[130]