Палестина оставалась провинцией Византии вплоть до 619 года. Ко второй половине V века относится постепенное уменьшение численности евреев в Эрец-Исраэль. Тем не менее, в Галилее даже в этот период сохранялось еврейское большинство.

В 614 году Палестина была завоёвана Персией и вошла в состав империи Сасанидов. Овладев, при поддержке евреев, Иерусалимом, персы передали его евреям. Однако, контроль над Иерусалимом оставался в руках евреев лишь в течение трёх лет.

После победы над Персией в 629 году византийский император Ираклий торжественно вступил в Иерусалим. Палестина снова стала византийской провинцией. В 629—630 годах, в результате массовых убийств и гонений на евреев, начатых Ираклием, еврейское присутствие в регионе достигло своего минимума за всю трёхтысячелетнюю историю. Тем не менее еврейское присутствие на Земле Израиля никогда не прекращалось полностью.

Около 636 года — в самом начале исламских завоеваний — Палестина была завоёвана у Византии мусульманами.

В последующие шесть веков контроль над этой территорией переходил от Омейядов к Аббасидам, к крестоносцам и обратно.

Эпоха арабского владычества в Палестине делится на четыре периода:

С 1099 по 1187 год крестоносцы основали здесь Иерусалимское королевство. Однако уже в 1187 году Салах-ад-Дин взял Иерусалим, а в 1291 году пала последняя крепость крестоносцев Акра.

В 1260 году Палестина перешла в руки династии Мамлюков.