Hadrianus rakennutti paikalle Afroditelle omistetun temppelin vuonna 135. Temppeli oli paikalla noin kahden sadan vuoden ajan. Konstantinuksen käännyttyä kristinuskoon 312 hän rakennutti monia kirkkoja Pyhälle maalle. Pyhän haudan kirkon rakennustyöt aloitettiin 326. Kirkon rakentaminen kesti yhdeksän vuotta, ja tuon ajan kristillisten historioiden mukaan Golgata löytyi rakennustöiden aikana.[1] Konstantinuksen äidin Helenan väitetään myös löytäneen Jeesuksen ja kahden ryövärin ristit.[2]

Persialaiset tuhosivat alkuperäisen bysanttilaisen rakennuksen vuonna 614. Sen tilalle rakennetun kirkon tuhosi egyptiläinen kalifi al-Hakim bi-Amr Allah vuonna 1009.[3] Kirkko korjattiin uudelleen 1048, kun keisari Konstantinos IX myönsi varat sen rakentamiseksi. Rahat eivät kuitenkaan riittäneet koko kirkon uudelleenrakentamiseen, ja vain piha ja rotunda säilyivät. Rotunda muutettiin kirkoksi, ja siihen lisättiin suuri apsis.[1]

Ensimmäisen ristiretken voitokkaat ritarit tulivat 1099 Pyhän haudan kirkkoon laulamaan ”Te Deumin” Jerusalemin valtauksen jälkeen. Ristiretken johtaja Godefroy de Bouillon julisti itsensä Pyhän haudan puolustajaksi. Ristiretkeläiset alkoivat laajentaa ja korjata kirkkoa vuonna 1112 romaaniseen tyyliin. He rakennuttivat ensin luostarin paikalle, jossa Konstantinuksen basilika oli ollut. Jeesuksen haudalla ollut pyhäkkö korvattiin uudella 1119. Rakennukseen tehtiin laajoja muutoksia 1131 Fulkon ja Melisenden kruunajaisia varten. Konstantinuksen aikainen piha katettiin romaanisella kirkolla. Se yhdistettiin rotundaan rakennelmalla, joka tuhosi 1000-luvulla tehdyn apsiksen. Kellotorni rakennettiin 1170.[1]

Ristiretkiajalla kirkon kolme tärkeintä hoitajaa määrättiin. Hoitotehtävä annettiin kreikkalaisortodokseille, armenialaisapostolisille ja katolisille. Koptit, Etiopian ortodoksit ja syyrialais-ortodoksit saivat 1800-luvulla pienempiä vastuualueita. Kirkkojen keskenäisten sopimusten mukaan sovitaan kirkon jumalanpalveluspaikoista ja -ajoista.[1]

Jeesuksen haudaksi uskottu holvi avattiin poistamalla sitä peittävä 1 x 2 metrin kokoinen marmoripaasi lokakuussa 2016 ensimmäistä kertaa satoihin vuosiin. Hautaa tutkivat ja restauroivat pääasiassa kreikkalaiset arkeologit kevääseen 2017 saakka.[4]