Город, основанный на месте военного лагеря полководца Амра, был назван «Фустат» («палатка»). Вскоре здесь была возведена мечеть полководца Амра, которая в то время мало чем отличалась от обыкновенных жилищ. Это была небольшая и низкая сырцовая постройка с посыпанным галькой полом и плоской глиняной крышей на пальмовых столбах. В ней не только совершались религиозные отправления мусульман, мечеть служила также залом для совещаний, суда и… приютом.
По мере того как приходила в упадок Александрия, роль Фустата возрастала, и к середине VIII века он превратился в политический и экономический центр Египта. По углам мечети Амра появились невысокие надвратные башни, потом многие правители подновляли и украшали эту мечеть, а в 827 году она подверглась коренной перестройке. Тогда мечеть была расширена в два раза и достигла своих нынешних размеров. Каирцы называют мечеть Амра «венцом мечетей», и не только за ее древность, размеры и грандиозность форм: именно в ней верующие всех исповеданий, признающие единого Бога, не раз собирались на молитвы в годину общих испытаний.
Решительный перелом в истории Фустата произошел во время правления Ахмеда ибн Тулуна – личности незаурядной, хотя он был сыном тюркского раба. При нем на склонах Мукаттам был возведен обширный дворец, а ближе к холму Яшкур заложен новый город. Если прежний Фустат рос довольно стихийно, то план новой правительственной резиденции был продуман весьма тщательно, поэтому со временем город из провинциального центра превратился в столицу страны. Ахмед ибн Тулун назвал свою новую столицу «Мизр» («Блистательная»), и это имя у средневековых авторов закрепилось и за Фустатом.
В 904 году халифы Багдада вернули себе власть над Египтом и сровняли с землей дворец строптивого Тулуна. Однако построенную им в 879 году мечеть они не тронули, и она до сих пор является украшением Каира. Легенда рассказывает, что план мечети был прислан халифу первым христианским архитектором, томившимся в тюрьме. В Фустате строились не только мечети, но и христианские церкви, самой значительной из которых является церковь Святого Сергия.
Со временем Аббасидам становилось все труднее удерживать власть над разнородными частями своей обширной империи, и в 969 году войска династии Фатимидов почти беспрепятственно заняли Фустат. Недалеко от него был заложен новый город, в котором уже через два года была расквартирована их армия и в общих чертах закончено возведение мечети и дворца. В 972 году аль Муизз, халиф мусульманской династии Фатимидов, торжественно вступил в свою новую столицу, названную «аль-Кахира» («Победоносная»).
По поводу этого названия в ученом мире существуют две версии. Как рассказывают восточные хроники, такое название новому городу было дано не только «в память одержанных Фатимидами побед, но и как предзнаменование будущих, которые небо пошлет им над их врагами». По другой версии, город получил свое название в честь планеты Марс, которую арабы называют аль-Кахира.
По представлениям арабов Марс – несчастливая планета, но вопреки предзнаменованию город все же назвали «Победоносным». Несколько позднее в новом городе появились итальянцы, которые сокращенно стали называть его Каиро, за ними и другие европейцы начали именовать его каждый по-своему, например, французы называют его Кэр.
При строительстве Каира материалом служили главным образом камни из развалин древнего Мемфиса, Фустата и пирамид фараонов. Эти камни отличались необыкновенной прочностью, даже и сейчас в стенах какой-нибудь старинной кладки можно обнаружить камни, испещренные древними иероглифами.