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