Amr bin Alas, was an Arab military commander who is most noted for leading the Islamic conquest of Egypt in 640-41. When he entered Egypt he founded the city of Fustat, and built his mosque there in 21H (642). It was a very simple building and measured 17 X 29 Meter. Its walls were built of mud brick and the roof was constructed of split palm trunks, supported by palm trunk columns, and covered with a thatching of palm leaves and mud. The floor was strewn with pebbles. Nothing whatever remains of the first mosque, on account of the numerous rebuilding.

History, however, has recorded the successive alterations and modifications which this mosque has undergone from its foundation down to the present day. Its area was extended, the roof was raised, the palm trunk columns were replaced by marble ones, the walls were decorated, the number of entrances was increased, and many features of architectural importance were introduced. In the year 53H (672-673), Muawiya ordered Maslama ibn Mukhallad, Governor of Egypt, to build the four sawami' (towers) , similar to those which stood at the corners of the old temple of Damascus; access to these sawami' was effected by means of outside ladders. These sawami' or square towers, were actually the origin of the minarets which were built in Egypt; later on a number of types were evolved, some of elaborate design. Another architectural feature which was introduced later on in this mosque was the concave mihrab, which was copied by Quran ibn Sharik from that erected by 'Omar ibn 'Abd Al-Aziz in the mosque of Madina in 88H (706-707) ; the first mihrab had been flat.
 

In 212H (827) , 'Abd Allah ibn Tahir, who had been appointed Governor of Egypt by the 'Abbasid Khalif Al-Ma'mun, ordered that the mosque be doubled in size, by the addition to the west (S.W.) of its exact area. Its dimensions then became about 112 X 120 meter. This was the last recorded extension of the mosque proper, and its area has remained unchanged up to the present day. It then consisted of an open Court, surrounded by four hallways . The sanctuary had seven arcades parallel to the Qibla wall and extending for the whole width of the mosque. The back hallways was similar; the side hallways had seven arcades, parallel to the Qibla wall, and extending from the side walls up to the Court. The mosque had thirteen entrances, three in the north wall, five in the east, four in the west and one in the Qibla wall. In the upper part of the walls was a row of windows, between each two of which was a niche with a fluted hood. The fragments of timber architraves, placed over the capitals of columns, next the west wall of the Qibla hallways , are of the greatest importance, for their carved decoration shows that they must belong to the time of 'Abd Allah ibn Tahir, 212H (827).