في أوائل القرن السابع الميلادي، نجح الخليفة الأول من الخلفاء الراشدسن، أبو بكر، في توحيد القبائل العربية في شبه الجزيرة العربية تحت راية الإسلام، الدين التوحيدي الثالث الناشئ من المنطقة. وبالتالي دعا المؤمنين إلى حرب مقدسة أو الجهاد لنشر الإسلام خارج حدود شبه الجزيرة العربية. توفي أبو بكر عام 634 م خلال المراحل الأولى من الفتح، ولكن خلفه، الخليفة عمر بن الخطاب، انتصر في معركة حاسمة عند نهر اليرموك ضد الجيش البيزنطي للإمبراطور هرقل عام 636 م، وسقطت القدس وقيصرية عامي 638 و 640 على التوالي.
قسم عمر فلسطين إلى مقاطعتين (جند)، كما كان الحال في ظل الحكم الروماني والبيزنطي. تضمنت مقاطعة الأردن الجليل وعكا، بينما تضمنت مقاطعة فلسطين (جند فلسطين)، مع عاصمتها في اللد وفي وقت لاحق في الرملة، كل الأراضي جنوبي سهل زرعين (مرج بن عامر). وتم إعلان القدس كثالث أقدس مكان في الإسلام. وأصبح جبل الهيكل الحرم الشريف وتم بناء مسجد في جوار الهيكل السابق، وهو المسجد الأقصى. وسرعان ما بدأت عملية تعريب فلسطين، وأما أسلمتها فاستغرقت وقتاً أطول.
الأمويون هم أول حكام فلسطين في ظل الإسلام، وهي السلالة التي برزت بعد اكتساب السلطة من الحكام الذين كانت قاعدة حكمهم في مكة والمدينة. عام 690 م، شيد الخليفة عبد الملك بن مروان قبة الصخرة، وهي صرح مثير للإعجاب على قاعدة هيكل سليمان.
انتهى حكم الأمويين حوالي عام 750 م، عندما تولت الخلافة العباسية من بغداد، ولكن من وقت لآخر كان هناك انتفاضات قامت بها مجموعات في فلسطين بقيت موالية للأمويين. حوالي عام 980 م، احتلت السلالة الفاطمية من شمال أفريقيا، مصر، ولاحقاً فلسطين. عانت المنطقة تحت حكم الخليفة الفاطمي الحكيم، والذي أصدر تدابير تمييزية ضد السنّة والمسيحيين واليهود على حد سواء. عام 1017، أمر بتدمير أهم معبد مسيحي في القدس، وهو كنيسة القيامة. عام 1009، فقد الفاطميون السيطرة على القدس، عندما دخل الصليبيون فلسطين من أوروبا الغربية.
