De plek waar kruisigingen destijds plaatsvonden was een steengroeve. Op een hoog punt aan de rand van de groeve zou Jezus gekruisigd zijn en vervolgens zou zijn lichaam zo'n 43 meter verderop in een uitgehakte ruimte zijn gelegd. In deze groeve zijn later meer Joodse graven gevonden.[1] Al een paar jaar na de kruisiging werd de stad uitgebreid waardoor het graf binnen de stadsmuren kwam te liggen.

In de 2e eeuw liet Keizer Hadrianus de groeve dichtgooien met puin en daarbovenop een tempel bouwen die gewijd was aan de godin Venus. Hadrianus deed dit vermoedelijk om de plek te ontheiligen en zo het groeiende Christendom tegen te gaan. Volgens sommige bronnen werd op de rots van Golgotha een beeld van Venus geplaatst.[1] Ook was de tempel onderdeel van de herbouw van Jeruzalem nadat de stad zwaar beschadigd was na eerst de Joodse Oorlog en daarna de Bar Kochba-opstand.[2][3]

Toen in de vierde eeuw Keizer Constantijn de Grote het christendom als geloof aannam, werd de tempel vervangen door een kerk. Hiervoor werd de onderliggende groeve grotendeels uitgegraven en onderzocht. Hierbij zouden een aantal relikwieën gevonden zijn, waaronder de Relikwieën van het Heilige Kruis die door de moeder van Constantijn zelf gevonden zouden zijn. Op deze vindplaats werd de ondergrondse Inventio Cruciskapel gebouwd. Toen het graf werd gevonden werden de rotsen eromheen grotendeels uitgehakt en hier werd een Aediculum (klein tempeltje) omheen gebouwd. De kerk bestond uit twee gebouwen, voor de rots en voor het graf, die door een binnenplaats met elkaar verbonden waren.[1] De kerk werd in 335 ingewijd. Daarnaast werden in het Heilige Land nog twee kerken gebouwd. Deze werden gebouwd in opdracht van Macarius, destijds de bisschop van Jeruzalem.

Het gebouw werd bij de verovering van Jeruzalem door de Perzen onder sjah Khusro II in 614 zwaar beschadigd. De kerk werd later gerestaureerd. Op bevel van de Fatimidische kalief Al-Hakim werd de Heilig Grafkerk in 1009 met de grond gelijk gemaakt. Al-Hakim, die geloofde een incarnatie van God te zijn en zeer puriteins was in zijn geloofsopvattingen, kon het niet verdragen dat zo'n belangrijke christelijke kerk in zijn rijk stond. Hij gaf opdracht om de "Kerk van de mestvaalt" zoals de moslims de kerk spottend noemden, te plunderen. (De Kerk van de Mestvaalt of Kanisat al-Qumana is een woordspeling op Kanisat al-Qiyama, de Arabische naam van de kerk.) Nadat zijn mannen eerst alle schatten van de kerk geroofd hadden, werd de kerk tot op de kale rotsbodem steen voor steen afgebroken. Zelfs de fundamenten werden weggehaald. Ook het graf van Jezus werd vernietigd. Wat nog restte werd in brand gestoken.[4]

Al-Hakim werd uiteindelijk waanzinnig en haalde zich de woede van de moslims op de hals, omdat hij zich had laten uitroepen tot een incarnatie van God; hij verdween onder mysterieuze omstandigheden in 1021. Zijn opvolger kalief al-Zahir kreeg het gezag over Jeruzalem pas acht jaar later, in 1029, in handen. Hij beloofde de christenen dat zij een nieuwe Heilig Grafkerk mochten bouwen.[5] In 1042 begon de Byzantijnse keizer Constantijn IX Monomachos met de wederopbouw van de Heilig Grafkerk, die in 1048 werd voltooid.

In 1099, met de Eerste Kruistocht werd Jeruzalem ingenomen. Hierna werd begonnen met de bouw van de huidige kerk waarbij zowel het graf als de rots in één gebouw werden opgenomen. De kerk werd in 1149 ingewijd maar later nog wel een paar keer verbouwd.