Существует версия, что Амр намеревался сделать Александрию своей столицей, что было бы вполне естественным, однако этому воспрепятствовал халиф Умар, опасавшийся христианского и эллинистического влияния большого города. Поэтому правитель со своим войском обосновался к северу от крепости Вавилон на участке земли, ставшем зародышем старого Каира. Египетско-арабская традиция утверждает, что так решил сам халиф Умар, который, как и в случае с Куфой и Басрой, не желал, чтобы арабские войска отделяла от Аравии водная преграда. В то же время участок занимал удачную стратегическую позицию в верховьях дельты, всего в нескольких километрах от Мемфиса — столицы фараонов. Здесь была построена первая мечеть. Хотя большую часть ее составляют позднейшие перестройки, она до сих пор известна как мечеть Амра и находится на том же месте, где он ее выстроил. Вокруг мечети арабы разбили свои шатры и выстроили хижины. Названия поселившихся здесь племенных групп заботливо сохранялись египетско-арабской традицией, и на протяжении еще двух веков предки, пришедшие сюда с армией завоевателей, обеспечивали потомкам не только социальный престиж, но и долю в налоговых поступлениях. Списки показывают, что большую часть поселенцев составляли арабы с юга, из оседлых областей Йемена и Хадрамаута в Южной Аравии. Поселение получило название Фустат, то ли от одного из арабских слов, обозначающих шатер, то ли от искаженного греческого «фоссатон», то есть «ров».
В сравнении с новозаложенными арабскими городами, такими как Куфа и Басра, где с самого начала прокладывались широкие улицы и намечался городской центр, Фустат выглядел более беспорядочным и стихийным. Разные племена и семьи селились где вздумается, а улицы вырастали из извилистых тропинок, тянувшихся к Нилу, к мечети и рынку. Поселение было очень разбросанным, составляя 5 километров в направлении север—юг вдоль реки, и почти километр в направлении запад—восток. Люди держались родственными группами, и каждой группе от 30 до 350 человек выделялся «хита», или участок для строительства домов. Поначалу Фустат, как говорит величайший из его историков, «был конгломератом тридцати или сорока племен (или племенных союзов), состоявшим из нескольких сотен палаток и хижин из глины и тростника, построенных более или менее кучно и разделенных большими пространствами необитаемых земель». Более свежие археологические исследования подтверждают, что в эпоху арабских завоеваний здесь было много незастроенных участков и что строительство постоянных кирпичных домов началось на очень ранней стадии.
Это беспорядочное поселение ожидало славное будущее. С 641 года, когда его основал Амр, и по сей день город в верховьях нильской дельты остается столицей Египта. Правда, центр власти постепенно смещался на север, через заложенные в IX веке правительственные кварталы на северной границе Фустата к обнесенному стеной Каиру (ал-Кахира, Победоносная), основанному Фатимидами в 969 году, но вопреки этой медленной миграции к северу Фустат оставался жилым и торговым центром до 1117 года, когда его почти целиком сожгли в страхе перед угрозой вторжения крестоносцев. С 1117 года участок лежал в руинах, и низкие курганы обломков скрывали под собой остатки домов, мечетей и бань. А вот старая крепость Вавилона осталась центром коптской веры и культуры, и мусульмане все еще почитают мечеть, носящую имя Амра, как старейшую в Египте.
С основанием Фустата Александрия перестала быть столицей. Почти тысячелетие Египтом правила грекоязычная элита этого приморского города. Александрия легко и постоянно поддерживала контакт с Римом и Константинополем. За время перемирия между переговорами о сдаче города и прибытием в него арабского гарнизона большая часть элиты выехала. Александрия стала пограничным городом. В конце 645 года ромейские войска под командованием Мануила высадились в Александрии и легко заняли город. Оттуда они начали вылазки по дельте, однако не сумели развить преимущество и атаковать Фустат. Амр, к тому времени смещенный с поста наместника, был спешно возвращен на это пост и возглавил войско с тем же успехом, что и при первом завоевании. Византийцев оттеснили обратно в Александрию. К лету 646 года город оказался в осаде. Есть сообщения, что мусульмане сокрушили стены города с помощью осадных машин, другие рассказывают о предательстве одного из стражей у ворот. Доказать ту или иную версию невозможно, однако ясно, что город был взят силой: часть ромейских солдат спаслась на кораблях, однако многих, включая и Мануила, убили в сражении. На сей раз вступление арабов в город сопровождалось большими пожарами и бойней, пока Амр не положил конец избиению на месте, известном с тех пор как Мечеть Милости.