Арабским административным центром Египта с 642 г. стал военный лагерь Фустат, расположенный в нескольких сотнях метров к северу от Вавилона, вдоль берега Нила и дальше от реки на седловидной пустынной возвышенности, протянувшейся с юга на север на 4 км. Название, по мнению исследователей, происходит от арабизированного лат. «fossatum» – «ров, полевое укрепление». В папирусной документации употреблялось также двойное наименование Фустат-Миср (Фустат Египетский) или просто Миср (Мыср, Маср) – древнее семитское название Египта, обозначавшее теперь его административный центр. Территория города соответствовала территории современного Старого Каира (Маср-эль-Атика). Здесь Амр построил первую в Египте мечеть, названную его именем (впоследствии неоднократно перестраивалась, современные план и размеры были определены в 827 г.). Земля в радиусе около 2 км была разделена между арабскими племенами; палатки, глинобитные дома и загоны для скота чередовались с обширными пустырями. Фустат не имел стен. Наплавной мост соединял его с островом Рода на Ниле и Эль-Гизой. Чуть севернее Фустата, между Нилом и Красным морем, со времён древнего Египта существовал канал Халиг (восстановлен в 643 г., заброшен в середине VIII в. и с тех пор стал прудом к северу от Каира). В Фустат поступали все налоговые взносы из Египта; экспорт зерна, ранее отправляемого через Александрию в страны Средиземноморья, теперь шёл через Фустат в Мекку. Это способствовало быстрому упадку Александрии и развитию новой столицы. Выделялись кварталы для новых поселенцев, зиммиев (немусульман); в Фустате появились христианские коптские храмы. Фустат и Вавилон постепенно слились в одну агломерацию, после VII в. их перестали различать, и термин Вавилон (Бабальюн) вышел из употребления у арабов. В коптской среде он, напротив, сохранился и иногда применялся для обозначения всего массива поселений Каира. Это же название для Каира использовали и некоторые европейские путешественники Средних веков и Нового времени. Постепенно Фустат приобрёл городской облик, строились крытые рынки, бани, казнохранилища. Египетские наместники исламского халифата основывали новые административные кварталы вокруг своих резиденций. Так, губернатор Египта конца VII в. Абд аль-Азиз ибн Мерван развивал район Хелуан (Хельван) к югу от Фустата. К востоку от города, между Фустатом и отрогами горы Эль-Мукаттам, было расположено кладбище Эль-Карафа. По оценкам исследователей, до середины IX в. Фустат занимал площадь около 600 га, и только территория вокруг Бабальюна и мечети Амра (70 га) была застроена плотно. Численность населения к IX в. оценивается в 85–100 тыс. человек, к началу Х в. – в 200 тыс. человек. Во второй половине IX в., в период распада халифата, Египет перешёл под власть династии Тулунидов. Её основатель Ахмад ибн Тулун построил к северо-востоку от Фустата новую резиденцию – квартал Эль-Каттаи («наделы»). Мечеть Ибн Тулуна (878–879 гг.) является старейшим зданием Каира, сохранившимся в первоначальной форме. Её зодчий-христианин, по мнению исследователей, из Месопотамии, взял за основу проекты мечетей Самарры IX в. Прочие постройки резиденции Тулунидов (дворец, сады, административные здания) были разрушены в 905 г., когда Египет был на время возвращён под власть Аббасидов.