Selama periode Bizantium (mulai tahun 390 M), wilayah yang sebelumnya merupakan bagian dari Kekaisaran Romawi didominasi oleh agama Kristen di bawah pemerintahan Bizantium. Pergeseran ini dipercepat dengan masuknya peziarah Kristen dan pembangunan gereja di situs-situs Alkitab.^[123] Para biksu juga berperan dalam mengubah agama pagan setempat dengan mendirikan biara di dekat pemukiman mereka.^[124]Komunitas Yahudi di Palestina mengalami kemunduran dan kehilangan status mayoritasnya pada abad keempat.^[125] Pembatasan terhadap orang Yahudi meningkat, termasuk larangan membangun tempat ibadah baru, memegang jabatan publik, dan memiliki budak Kristen.^[126] Kepemimpinan Yahudi, termasuk kantor Nasi dan Sanhedrin, dibubarkan pada tahun 425, dan pusat Yahudi di Babilonia menjadi terkenal setelahnya.^[123]Abad ke-5 dan ke-6 menyaksikan pemberontakan Samaria melawan pemerintahan Bizantium, yang berhasil ditindas, mengurangi pengaruh Samaria, dan memperkuat dominasi Kristen.^[127] Catatan perpindahan agama Yahudi dan Samaria ke agama Kristen selama periode ini terbatas dan sebagian besar berkaitan dengan individu dan bukan komunitas.^[128]Pada tahun 611, Khosrow II dari Sassanid Persia , dibantu oleh pasukan Yahudi, menyerbu dan merebut Yerusalem.^[129] Penangkapan tersebut termasuk penyitaan "Salib Sejati".Nehemia ben Hushiel diangkat menjadi gubernur Yerusalem.Pada tahun 628, setelah perjanjian damai dengan Bizantium, Kavad II mengembalikan Palestina dan Salib Sejati kepada Bizantium.Hal ini menyebabkan pembantaian orang Yahudi di Galilea dan Yerusalem oleh Heraclius , yang juga memperbarui larangan masuknya orang Yahudi ke Yerusalem.^[130]