In AD 640, the Moslem army, commanded by a skillful warrior, politician, and poet by the name of Amr Ibn-el-Aas, besieged the Fortress of Babylon. It was a matter of time before the Viceroy of Egypt, Cyrus, agreed to peacefully surrender the Fortress, and less than a year later, the Capital city Alexandria. Amr became the first Arab ruler of Egypt and remained so until his death.
Even tough the Arabs admired Alexandria's glamor and wealth, they decided to abandon the city. The reason is simple: no body of water was to separate the Egyptian Capital from the Caliph's residence in Medina. Al-Fustat was therefore founded on the East bank of the Nile, outside the walls of the Fortress of Babylon. Deriving its name from the Arabic (and Roman) word for "camp" or "tent", the town was built at the spot where the Arabs camped during the Fortress siege. Here, the first Mosque in Africa was built, carrying the name of the Arab general, Amr.
The new Capital grew slowly as Alexandria declined. With the re-opening of the Red Sea Canal, Al-Fustat became the linking bridge between the East and the West. In AD 661, a power struggle took place over the Islamic Caliphate, and Amr, the cunning politician, sided with the powerful Umayyads who ruled from Damascus, and even played a major role in legitimizing their reign. Egypt remained since loyal to the Umayyads until the collapse of their rule.
With the vast expansion of the Umayyad Empire, stretching from China to the east to Spain in the west, corruption was unavoidable. Their rule was violently ended in 750 by the Abbasids who moved their Capital to Baghdad. The new rulers moved the Egyptian Capital from Al-Fustat to the new town of Al-Askar. Although both towns were just a stone's throw away, it was their way of imposing a new order. The lavishness of the Abbasid Empire reached its highest point under the rule of Haroon al Rashid, but so did the taxes imposed on Egyptians. In 832, during the reign of the Caliph Maamoon, the mostly-Coptic Egyptians peasants revolted, and Maamoon traveled himself to Al-Askar to subdue them.
With the growing disorder within the Abbasid provinces, a new sort of rule came into existence by which local governors started to gain more power, and some sort of independence. These governors were mostly appointed by the Baghdad Caliphate, even though they were either elected by the locals or ascended to power through military struggle. In Al-Askar, such independence was eventually achieved in by a young governor named Ahmad Ibn-Tulun.
Ibn-Tulun's power over Egypt grew shortly after Maamoon appointed him. By AD 870, he declared Egypt an independent entity under the supreme rule of the Abbasid Caliph. Not surprisingly, the young man decided to build a new capital to confirm the new order. He founded Al-Qatai, not far from Al-Askar. In fact, Al-Fustat, Al-Askar, and Al-Qatai all cover an area of about 10 square kilometers, and constitute a small part of today's Cairo.
The implications of Ibn-Tulun's rule are much deeper than the founding of the city itself. For the first time since Cleopatra's death Egypt became an independent state, albeit under the rule of a foreigner. Taxes collected were no more sent to the Caliphate in Baghdad, and the army was no more under the Caliph's rule. And like earlier great rulers, Ibn-Tulun built a magnificent mosque immortalizing his name. Upon his death, he was succeeded by his son Khamaraweh, who notoriously spent his time and money on embellishing his palace and capital city.
In 905, the Tulunid dynasty was overpowered back by the Abbasids who destroyed the palace and devastated the gardens of Al-Qatai, and moved the capital back to Al-Fustat. Egypt, however, went into a state of anarchy that lasted for 30 years, until the next powerful ruler emerged. This time, he was a Turk who was appointed by Baghdad to restore order in Egypt. His name was Mohammed Ibn-Toughj, better known in history as Al-Ikhshid. Under his rule, the capital city grew to encompass the towns of Al-Askar and Al-Qatai. During the rule of Al-Ikhshid's successor, Kafoor, part of Al-Fustat was burned down. Not more than a few years later, the city's status as Egypt capital was forever put to an end by Egypt's new rulers: The Fatimids.