وبدأ محاصرتها فى جمادى الأولى سنة 13 هـ (يولية 634 م) ولكنه اضطر إلى التقهقر لاقتراب جيش بيزنطى جديد، وكان عمرو على استعداد لمواجهته ولكن بعد ضم قواته لتلك القوات التى جاء بها خالد من بلاد الشام، وقد استطاع عمرو بن العاص بعد الانتصار على البيزنطيين فى أجنادين فى جمادى الأولى أو الثانية (يولية، أغسطس 634 م) احتلال معظم مدن فلسطين مثل سبسطية (السامرة) ونابلس واللد ويُبْنى وعَمْواس وبيت جبرين ويافا وقد استطاع -بعد معركة اليرموك فقط- أن يواصل حصاره لإيليا (بيت المقدس) التى يقال إن أهلها رفضوا الاستسلام لأحد غير الخليفة عمر بن الخطاب الذى ذهب إلى الشام لهذا الغرض (16 هـ/ 637 م). أما بالنسبة لمدينة قيصرية، فقد حاصرها عمرو مرة أخرى، ولكنه تركها بعد ذلك ليذهب إلى مصر مخلِّفًا بها يزيد بن أبى سفيان الذى توفى بعد فترة قصيرة ليخلفه شقيقه معاوية الذى سيطر على المدينة واحتلها بالخديعة والحيلة فى العام التاسع عشر أو العشرين الهجرى 640 أو 641 م)، ثم أكمل فتح فلسطين باحتلال عسقلان.
وقد ترك الفاتحون العرب التنظيم الإدارى الموجود كما هو، ولكنهم غيروا اسم فلسطين الأولى إلى "جند فلسطين"، وأقاموا العاصمة فى بادئ الأمر فى اللد، وبعد ذلك فى الرملة، هى مدينة جديدة أسسها سليمان بن عبد الملك عندما كان واليا على فلسطين، والتى واصل الإقامة فيها بعد أن أصبح خليفة فى عام 99 هـ/ 715 م، ولا تزال "جند فلسطين" ترد على هذا النحو عند "ابن شداد"، وقد بقيت كإقليم إدارى حتى الغزو المغولى، ولكن يبدو أن حدودها قد اتسعت إلى ما وراء ذلك منذ القرن الرابع الهجرى (العاشر الميلادى) وامتدت شرقا وجنوبا وناحية الجنوب الشرقى. ويذكر "المقدسى" -الجغرافى المشهور- أريحا، وعَمَّان التى كانت تعرف قديما باسم فيلادلفيا ويدخلهما بين دول هذا الإقاليم، وقد تبعه فى ذلك ياقوت الحموى"، أما الاصطخرى وابن حوقل، فيضمان إلى فلسطين جنوب الغور و"الجبال"