In het jaar 324 Helena, moeder van Keizer Constantijn, de eerste Christelijke keizer, kwam naar Jeruzalem en vond de overblijfselen van het Kruis in een ondergronds reservoir. Constantijn bouwde de eerste kerk op de plaats in de 4de eeuw (begonnen in 326, ingewijdt in 335).
De kerk omvat onder zijn dak de plaats genoemd Golgotha, dat is de plaats van een "schedel" of Calvarieberg, heuvel waar Jezus gekruisigd is, en een andere heuvel waar Joseph van Arimathea zich een graf had gekocht in een begraafplaats die een niet meer gebruikte steengroeve was en de Grot van de Vondst van het Kruis. Constantijns' kerk werd in 614 vernietigd door de Perzen, onmiddellijk daarna herbouwd.
De kerk bleef tot 1009 intact toen alles behalve het graf en de structuur over de rots van Golgotha met de grond gelijk gemaakt werd door de Egyptische Fatimid Kalief Hakim. De Kruisvaarders herbouwden aan het eind van 11de eeuw de kerk en wat we vandaag zien is voornamelijk uit die periode.
De ingang naar de kerk is door een enkele deur in de zuidelijke transept (dwarsschip). De sleutel tot de toegang wordt door de Moslim familie van Nuseibeh gehouden, wie door Saladin in 1178 het voogdijschap werd toevertrouwd om de vrede te houden tussen de diverse Christelijke facties. Na periodes van spanning tussen de Nuseibeh familie en de Ottomaanse overheid in de 18de eeuw, benoemden de Ottomaanse autoriteiten de familie Joudeh om Nuseibeh in hun taak bij te staan. Vandaag, staat de Joudeh familie Nuseibeh nog steeds bij door de sleutel van de kerk aan een lid van de familie Nuseibeh te brengen die de deur op een dagelijkse basis opent en sluit.
Politiek van de Kerk: Sinds de Kruistochten, zijn het terrein en de constructie van de Heilige Grafkerk in bezit gekomen van drie belangrijke groeperingen: de Grieks Orthodox, de Armeneens Orthodox en (Latijnse) Rooms-katholiek. Andere gemeenschappen - de Egyptisch Koptisch Orthodox, Ethiopisch Orthodox en Syrisch Orthodox - bezitten ook bepaalde rechten en kleine eigendommen in of om het gebouw. De rechten en de voorrechten van elk van deze gemeenschappen worden beschermd door de Status-quo van Heilige Plaatsen (1852), zoals gewaarborgd in Artikel LXII van het Verdrag van Berlijn (1878).
Boven de hoofdingang zijn twee vensters waar u een korte ladder kunt vinden die een deel is van de facade van de Heilige Grafkerk wegens de ' Status-quo'. "Het probleem komt door het feit dat de twee vensters hierboven tot de Armeniërs behoren en zij het recht hebben hen schoon te maken en te herstellen, en de deklijst waarop de ladder steunt behoort tot de Grieks Orthodoxen. In sommige opzichten, ( vorige eeuw) staken de Armeniërs de ladder uit om het werk aangaande de vensters te doen, en de Grieken protesteerden dat de ladder op hun gedeelte rustte. De Armeniërs weigerden om de ladder te verwijderen - vandaar de bevroren werkelijkheid".