The Islamization of Palestine occurred as a result of the Islamic conquest in 640. It was a long process that included immigration of Muslim Arabs, as well as other Muslims, from other regions, as well as conversion to Islam by some of the indigenous Christian, Samaritan and Jewish population of the area. Islam did not become the majority religion of Palestine until at least the 9th century and possibly even as late as the Mamluk era (1250–1516). This occurred simultaneously with acculturation of the locals into Arab identity and the establishment of Arabic as the lingua franca, which eventually became their sole vernacular.
The Muslim Arab army attacked Jerusalem, held by the Byzantine Romans, in November, 636. For four months the siege continued. Ultimately, the Orthodox Patriarch of Jerusalem, Sophronius, agreed to surrender Jerusalem to Caliph Umar in person. Caliph Umar, then at Medina, agreed to these terms and traveled to Jerusalem to sign the capitulation in the spring of 637. Sophronius also negotiated a pact with Caliph Umar, known as the Umariyya Covenant or Covenant of Omar, allowing for religious freedom for Christians in exchange for jizya, a tax to be paid by conquered non-Muslims, called "dhimmis." Under Muslim Rule, the Christian and Jewish population of Jerusalem in this period enjoyed the usual tolerance given to non-Muslim theists.
Having accepted the surrender, Caliph Umar then entered Jerusalem with Sophronius "and courteously discoursed with the patriarch concerning its religious antiquities". When the hour for his prayer came, Umar was in the Anastasis, but refused to pray there, lest in the future the Muslims should use that as an excuse to break the treaty and confiscate the church. The Mosque of Omar,opposite the doors of the Anastasis, with the tall minaret, is known as the place to which he retired for his prayer.
According to the historian James William Parkes, during the 1st century after the Arab conquest (640–740), the caliph and governors of Syria and the Holy Land ruled entirely over Christian and Jewish subjects. He further states that apart from the Bedouin in the earliest days, the only Arabs west of the Jordan were the garrisons.