Nearly a thousand years of Greco-Roman rule in Egypt came to an abrupt end in 641 AD when an army of Arab Muslims lead by Amr Ibn Al-Aas captured Alexandria. Islam was only a few decades old at the time. The Prophet Muhammad had died in 632 AD, leaving the Muslim community in the Arabian Peninsula under the leadership of a succession of his companions, who oversaw the quick expansion of the Rashidun Caliphate to control much of North Africa, the Levant, and Persia by 661 AD.
The arrival of Islam in Egypt was very well-time. Egypt had only recently been reclaimed by the Byzantine Empire after briefly being conquered by the Persian Sassanid Empire. Additionally, the Egyptian Coptic Christian majority was suffering persecution under their Byzantine governors due to a theological disagreement between the Coptic Church and the Byzantines. The zeal of the Byzantines to stamp out this divergent theology in Egypt made it easy for the Egyptian Christians to accept the Muslim conquest, given that the Rashidun Caliphate asked only that non-Muslims in conquered lands pay a tax in return for exemption from military service in the Rashidun army.
After conquering Egypt, Amr Ibn Al-Aas founded a new capital called Fustat to cement his control at the site where his army had camped during their siege of the Roman fort of Babylon. Both the ruins of this fort and the site of the mosque itself can still be visited today in Coptic Cairo (Old Cairo). Egypt has remained under the control of various Muslim governments up until the modern era. The Rashidun Caliphate gave way to the Umayyad Caliphate, which was based in Damascus. In the 8th century the Abbasids Caliphate formed in Baghdad after a revolt against the Umayyads. In the 9th century the Fatimid Caliphate, originating in modern Tunisia, wrested control of Egypt from the Abbasids and established a new capital called Al-Qahirah from which modern Cairo takes its name. In 1171 AD the Fatimids gave way to the Ayyubid Caliphate, founded by the famous general of the Crusades, Salah Ad-Din.
Through all of these changes in government Egypt remained an important part of the Muslim world. As under Roman and Greek rule, the Nile Valley was of great economic importance as a producer of grain. In addition, under the Fatimid and Ayyubid Caliphates, Egypt and the capital, Cairo, were of great geographic and political importance. The beautiful buildings that still decorate Islamic Cairo are evidence of the wealth and influence that came to Cairo as the capital of the these important governments. During these centuries, the people of Egypt also changed with their government. Gradually Egyptians converted to Islam. At times the tax burden on non-Muslims was very high, in contrast to the mild treatment of non-Muslims by the Rashiduns, making conversion a practical matter. The rate of conversion increased especially during the Crusades when the conflict between European Christians and the Muslim government increasingly politicized religion; however, it is difficult to say specifically when Islam overtook Christianity as the most common religion in Egypt.