De 30 a.C até 641 d.C o Egipto permaneceu uma província romana e posteriormente bizantina esmagada pelo declínio em todos os sectores da vida. Ao longo dessa Época em que as condições políticas e econômicas foram em plena deterioridade, os egípcios coptas ortodoxos eram sujeitos a incessante perseguição dogmática por parte das autoridades romanas. Portanto, em 641 d.C, quando "Amr Ibn Al-Ass", o comandante muçulmano árabe, conquistou o Egipto liderando uma campanha contra os romanos bizantinos, foi bem recebido como auténtico libertador pelos nativos. Os coptas cristãos ortodoxos do Egipto ajudaram o exército dos muçulamnos pelo menos a nível logístico até conseguiram tomar a fortaleza romana de Babilónia situada no sul do Cairo actual depois de um cerco prolongado de sete meses. Na sequência da queda da fortaleza de "Babilónia", as tropas romanas se transformaram em posição defensiva abrigadas na capital Alexandria. Amr marchou para conquistar Alexandria, e colocou a cidade sob um pleno cerco por uns meses, no entanto, o imperador bizantino Herácleo morreu e a sua viúva Martina aceitou a retirada das tropas romanas de Alexandria. Ela convocou Ciros ( Muqauquis ), o então exiliado ex-governador bizantino do Egipto para negociar com os árabes muçulmanos na base da retirada das tropas romanas sãs e salvas da cidade de Alexandria. Assim o pacto da retirada foi assinado entre os dois lados e finalmente as tropas romanas retiraram de Alexandria em 642 d.C. Porém em 654 d.C os romanos bizantinos tentaram de reconquistar Alexandria de novo com enormes falanges trasladadas a bordo de uma grande marinha, mas essa campanha militar foi um pleno fracasso para os bizantinos e Manuel, o comandante das tropas romanas foi cativado. Outro pacto de retirada foi assinado e a partir de então o Egipto se transformou num país pertencente ao Mundo Islâmico. A tolerância baseada nas regras do Islão e o bom-tratamento recebido pelos novos invasores tomaram os corações dos egípcios e pouco a pouco começaram a convertir-se ao Islão sem força, mas o processo da plena arabização do país demorou até o século X.

Conforme os acontecimentos da conquista, o exército árabe acampou-se na área vazia e vasta detrás da fortaleza de Babilónia, e ali, como seria de esperar, Amr mandou remontar a fundação da nova capital, chamada “Al Fustat ”, localizada no sul do Cairo actual. Al Fustat era a primeira Capital Islâmica estabelecida no Egipto e no continente africano. O nome "Al-Fustat " significa em árabe “tenda”. Uns historiadores relatam uma lenda sobre uma pomba que põe e incubou ovos sobre a tenda própria do alto comandante muçulmano Amr Ibn Al Ass, quem tinha ordenado desmantelar o acampamento antes do avance contra os romanos em Alexandria, e por tanto ao ver a pomba deixou-a em paz, rejeitando desmontar a sua tenda.

E outros acham que a palavra " Fustat" é derivada do termo grego “Fustatum ” que significa “forte, ou fortaleza”. De qualquer maneira Amr foi muito esperto no que diz respeito à escolha deste sítio privilegiado e estratégico, protegido pelo Nilo, no oeste, e pelas montanhas do Al-Moqatam no leste. A primeira mesquita que ainda permanece em pé, estava localizada no centro da nova cidade, rodeada de palácios e sede do governo e administração do país. A cidade cresceu-se mais a mais e foi coniserdada, de facto, uma das mais belas cidades no mundo islâmico, famosa pelas suas construções civís e religiosas como mesquitas, palácios, vivendas, fábricas e oficinas de artesanatos, banhos públicos, lojas e mercados distintos. Após a fundação do Cairo na Era Fatimita em 969 d.C, Al Fustat manteve desfrutar de uma grande época de esplendor cultural e econômico até 1169 ( 565 d.H) quando, infelizmente, Shauar o vizir do último califa fatimita Al-Aded mandou incendiar a cidade inteira a pretexto de impedir o avance dos cruzados no país. Infelizmente, tão incéndio devastador e desatroso resultou no desaparecimento da cidade antiga de Al Fustat

Os Fatimitas Shiítas estabeleceram um estado forte no norte da Àfrica mas o grande sonho deles foi tomar o Egipto, para o transformar na sede do seu poder crescente. Por isso tentaram de concretar esta cobiça duas vezes sem sucesso até em 969 d.C ( 258 H ) quando conseguiram, afinal, na terceira vez, conquistar o país sob o comando de Gawhar Al Siquili, o alto comandante do exército fatimita. Os Fatimtas não encontrarm uma resitência considerável. Na consequência disso O califa fatimita Al- Muiz Lidin-Ellah tinha ordenado o seu comandante Gawhar a estabelecer nova capital do paỉs e do califato fatimita inteiro. Gawhar escolheu um sítio privilegiado conhecido anteriormente como “Al- Manakh”, que foi, de facto, uma vasta área de terreno que fazia parte da extensão das três capitais anteriores; Al Fustat, Al Asskar, e Al Qatai. Segundo Al Maqruizi, um dos grandes historiadores da época, Gawhar mandou construir uma muralha circundante de adobes e antes do início das obras de construção convocou os astrónomos para lançarem um bom agouro a favor da nova cidade. Os astrónomos estenderam cordéis com campainhas através de pólos de madeira em torno do local traçado, pedindo aos trabalhadores começarem as obras de construção ao ouvir o toque das campainhas, no entanto, por acaso, um corvo aterrezou sobre um dos cordéis o que levou ao toque das campainhas e imediatmente o trabalhadores começaram as obras de construcão, achando que as campaninhas foram tocadas pelos astrónomos, então, os astrónomos gritaram “ Não, não, Al Qahir, senhor da órbita está no céu”. Al Qahir- em árabe "o vitorioso"- é o nome árabe do planeta Marte, e por isso a cidade foi nomeada de "Al-Qahira " ( o nome árabe do Cairo ). Outra versão insitse em que no início, o califa Al Muíz denominou a nova cidade “Al Mansouriah”, mas um pouco depois deu o nome de Al Qahira que significa em árabe a vitóriosa. O Cairo originalmente foi uma grande cidade real durante a Época da Dinastia Fatimita. O califa Al Muíz entrou o Cairo em 973 d.C , acompanhado por todos os membros da sua fámilia e a corte inteira, instalando-se no palácio construído por Gawhar e a partir de então o Cairo se transformou não só à capital do Egipto mas à capital de todo o Califato Fatimita. O Cairo durante o Período Fatimita era um centro, cultural, científico e artístico muito florescente na Idade Média. Depois de quase 200 anos da dominação fatimita shiíta, o Egipto regressa sob a liderança de Saladino, o fundador da Dinastia Ayubi, a doutorina sunita. Saladino ordenou abrir o Cairo real à habitação de todas as classes sociais em vez dos aristocratas, e a partir de então o Cairo se estendeu muito. Saladino mandou construir uma cidadela no leste do Cairo, e ligou as anteriores capitais ao Cairo através de uma muralha defensiva que se chama " a Muralha de Saladino".