In the early 7th century, the first of the Rightly Guided Caliphs, Abu Bakr, had succeeded to unify the Arab tribes on the Arabian Peninsula under Islam, the third monotheistic faith originating from the region. He subsequently called the faithful to a holy war or jihad to spread Islam beyond the boundaries of the Peninsula. Abu Bakr died in 634 during the first stages of the conquest, but his successor Caliph Umar ibn al-Khattab won the decisive Battle of Yarmouk against Emperor Heraclius’ Byzantine army in 636. Jerusalem and Caesarea fell in 638 and 640 respectively.
Umar divided Palestine into two districts (junds), as had been the case under Roman and Byzantine rule. The province of Jordan (Jund al-Urdunn) included Galilee and Acre, while the province of Palestine (Jund Filastin), with its capital in Lydda (Lod), and later in Ramla, comprised all the land south of the Plain of Esdraelon. Jerusalem was declared the third holiest place in Islam. The Temple Mount became al-Haram al-Sharif (The Noble Sanctuary) and near the former Temple a mosque was built, the Aqsa Mosque. The process of Arabization of Palestine quickly set in, Islamization however took longer.
The first dynastic rulers of Palestine under Islam were the Umayyads, a dynasty that had come to prominence after gaining power from the rulers whose power base was in Mecca and Medina. In 690, Caliph Abd al-Malik ibn Marwan erected the Dome of the Rock (Qubbat al-Sakhra), an impressive edifice on the foundations of the Temple of Solomon.
Umayyad rule ended circa 750, when the Abbasid dynasty from Baghdad took over, but from time to time there were uprisings by groups in Palestine which remained loyal to the Umayyads. Circa 980, the Fatimid dynasty from North Africa conquered Egypt and subsequently Palestine. The region suffered under the rule of the Fatimid Shia Caliph al-Hakim, who promulgated discriminatory measures against Sunnis, Christians and Jews alike. In 1009, he ordered the destruction of the most important Christian sanctuary in Jerusalem, the Church of the Holy Sepulchre. In 1099, the Fatimids lost control over Jerusalem, when crusaders from Western Europe entered Palestine.*