Amr ibn al-As, companion of the prophet and general of the Muslim armies, conquered the rich province of Egypt in 639. After taking Pelusium and the fortress of Babylon from Egypt, he set up a camp of tents north of it : the future Fustat, which will become Cairo. The legend reports that shortly before marching towards Alexandria, a dove comes to lay an egg in front of the tent of the Muslim general. After the victory of this one, judging the thing auspicious, he decides that on the site of the camp will rise the new capital of the country. In the center of the camp, the commander's tent is converted into a mosque, following the example of the Prophet Muhammad, who had done the same with his house in Medina.

The original layout was a simple rectangle 29 meters long by 17 meters wide. It was a low shed with columns made of split palm trunks, stones and mud bricks, covered with a roof of wood and palm fronds. The floor was gravel. Inside the building, the orientation towards Mecca was not noted by a concave niche as would be the case in all later mosques. Instead, four columns were used to indicate the direction of Mecca and were inserted on the qibla wall. It was large enough to provide prayer space for Amr's army, but had no other ornaments, nor minarets

Despite the fact that the vast majority of its original structure has been rebuilt and replaced, the historical importance of this mosque, as the first symbol of Muslim occupation and the first mosque in Africa, continues to make it a major tourist site. It is located in the district of Old Cairo, Fustat, close to the metro station of Mar Girgis and Coptic Cairo.