Nel 1009 dC il califfo fatimita di Egitto al-Hakim emise l'ordine esplicito di distruggere la Chiesa del Santo Sepolcro. Lo storico arabo Yahia Ibn Sa'id descrive così gli eventi: "Si impadronirono di tutte le suppellettili che si trovavano nella chiesa e la distrussero completamente, lasciando solo qualcosa la cui distruzione era molto difficile. Distrussero anche il Calvario e la chiesa del santo Costantino e tutto quello che si trovava nei loro confini e tentarono di eliminare i sacri resti… Questa distruzione cominciò il martedì il quinto giorno prima della fine del mese di Saffar nell’anno 400 dell’Egira (25 agosto 1009).

Per ben undici anni fu proibito ai cristiani di visitare questo sito e non era loro permesso nemmeno di pregare tra le rovine. Fu solo alcuni anni dopo che fu permesso ai cristiani di ricostruire il santuario. Questo fu il risultato di un trattato di pace tra l'imperatore bizantino Argyropulos e il successore di al-Hakim. I lavori furono iniziati sotto il regno dell'imperatore Costantino Monomaco.

Gli architetti imperiali, al loro arrivo a Gerusalemme, determinarono l'impossibilità di restaurare l'intera struttura costantiniana. Optarono così per la conservazione della sola Anastasis con l'aggiunta di un'ampia abside a oriente e di diverse piccole cappelle nell'area dell'atrio-giardino e del Martyrium. Questi lavori furono compiuti tra il 1042 e il 1048. Nel corso di tale ricostruzione l'Atrio orientale, il Martyrium e il portico-giardino scomparvero! E, con il restauro dell'Anastasis e del nuovo trono per il vescovo, scomparve per sempre l'afflusso piacevole della luce solare diretta!

Nonostante questi cambiamenti la nuova sistemazione non era sprovvista di componenti artistiche. Mosaici, ad esempio, coprivano le pareti e la cupola. L'abate russo Daniele, che ha visitato Gerusalemme nel 1006-1007, ci ha lasciato questa descrizione: "La chiesa della Risurrezione è di forma circolare ed è appoggiata su dodici colonne monolitiche e sei pilastri. Il pavimento è composto di bellissime lastre di marmo..

Ha sei porte e possiede tribune dotate di 12 colonne. Vivaci mosaici con i santi profeti si trovano sotto il soffitto e sopra le tribune. L'altare è sormontato da una immagine di Cristo. Sopra l'altare maggiore si può vedere un mosaico con l'Esaltazione di Adamo. Nell'abside, invece, è rappresentata l'ascensione di Cristo. L'annunciazione occupa i due pilastri vicino all'altare. La cupola della chiesa non è chiusa da una volta di pietra ma è fatta di travi di legno intrecciate tra di loro. La chiesa così ha una apertura alla sommità. Il Santo Sepolcro è collocato al di sotto di questa cupola aperta…"

Il pellegrino russo Daniele ha visto mosaici nella cappella della crocifissione sul Golgotha. Ha visitato la cappella della "Prigione di Cristo". quella del "Ritrovamento della Croce" e la cappella dedicata all'Apparizione di Gesù a sua madre, a nord dell'Anastasis.