В Фустате сохранялось христианское население. После ухода византийцев копты завладели почти всеми храмами и монастырями православных (мелькитов) в Египте, кроме церкви св. Михаила в Каср-эш-Шамъа. У исследователей нет сведений о других церквах Вавилона, существовавших до арабского завоевания, хотя город должен был иметь какое-то количество храмов. Из ныне существующих церквей Каср-эш-Шамъа древнейшей считается церковь святых Сергия и Вакха, связанная с преданием о пребывании Святого Семейства в Египте. Церковь Эль-Муаллака была возведена между бастионами, обрамляющими южные ворота Вавилона, предположительно в 680 гг. Храмы святых Кира и Иоанна (позднее великомученицы Варвары), великомученика Георгия и ряд других построил в конце VII в. сириец Афанасий, секретарь арабского наместника Египта. В первые века мусульманского правления, по мнению исследователей, небольшое число христианских храмов существовало на территории Фустата, к северу от Вавилона. Стены крепости Вавилон ограничивали пространство, из-за чего храмы теснились среди других построек. В Фустате, не имевшем стен, на просторных площадях строились церкви, однако их незащищённость заставляла возводить высокие ограды. Основание церкви св. Мины к северу от Фустата в 724 г. спровоцировало вооружённый конфликт одного из местных арабских лидеров с эмиром Египта, который разрешил её строительство. Негативное отношение части мусульман к сооружению новых церквей побудило наместника Египта Али ибн Сулеймана в 785 г. разрушить церковь Пресвятой Богородицы (Эд-Дамширия) и ряд других храмов в Фустате. Копты предлагали 50 тыс. динаров за разрешение восстановить церкви, но получили отказ. Однако уже через несколько лет новый наместник Муса ибн Иса позволил отстроить разрушенные храмы. Кафедра коптского епископа была перенесена из Вавилона в церковь св. Меркурия в Фустате (раньше 743 г., точная дата исследователям неизвестна). Хотя резиденция коптского патриарха формально оставалась в Александрии, патриархи часто и подолгу жили в Фустате. Здесь же состоялось избрание на патриаршество нескольких предстоятелей Коптской церкви: в 743 г. в церкви св. Шенуте в Фустате, в 858 и 975 гг. в церкви святых Сергия и Вакха. В городе проживало и некоторое количество православных. В конце VII в. придворные наместника Абд аль-Азиза из мелькитов получили разрешение построить церковь в Хелуане. Православные приближённые халифа аль-Мамуна, находившегося в Фустате в 832 г., выстроили церковь Пресвятой Богородицы (Канисат-эр-Рум – «церковь ромеев») на горе Эль-Мукаттам рядом с резиденцией халифа. Там же располагался православный монастырь Эль-Кусайр, настоятелем которого на рубеже VIII и IX вв. был Евстафий (впоследствии Александрийский патриарх). Он построил в монастыре церковь св. Апостолов и епископскую резиденцию. Хотя после восстановления православного Александрийского патриархата (731 г.) патриарший престол оставался в Александрии, центр церковной жизни мелькитов, как и коптов, постепенно перемещался в Фустат. Главы христианской общины Фустата были недовольны избранием патриарха Евтихия (933–940 гг.). Исследователи полагают, что большую часть времени он пребывал в Фустате и лишь перед смертью вернулся в Александрию.