Miejsce ukrzyżowania Jezusa i Jego grobu znajdowało się w opuszczonym kamieniołomie poza Jerozolimą. Golgota wraz z przyległym obszarem została włączona w obręb miasta dopiero w 44 roku, kiedy Herod Agryppa I zarządził budowę trzeciego odcinka muru obronnego. Mur ten, nieukończony przez króla, w pośpiechu kończyli powstańcy żydowscy w 66 roku. Po odbudowie Jerozolimy w II wieku (jako rzymskie miasto Aelia Capitolina) w tym miejscu zbudowano pogańską świątynię poświęconą bogini Wenus.
Pierwsza bazylika w tym miejscu została wybudowana w IV wieku z polecenia cesarza Konstantyna. Była ona trzykrotnie większa od współczesnej budowli – rozciągała się od obecnej rotundy, w której mieści się nad Grobem Jezusa.Budowla konstantyńska została zniszczona przez Persów pod wodzą Chosrowa II Parwiza, który w 614 zdobył Jerozolimę. Za panowania cesarza Herakliusza sanktuarium – w mniejszych rozmiarach – odbudował patriarcha Modest. Bazylika została jednak doszczętnie zniszczona w 1009 na polecenie kalifa Al-Hakima. Po 1099 r. Jerozolima została stolicą Królestwa Jerozolimskiego. Świątynia okazała się zbyt mała na potrzeby liturgiczne krzyżowców, więc przystąpili do przebudowy bazyliki, która trwała do 1149. W toku prac wyburzyli wschodnią absydę, wybudowali w tym miejscu kościół romański i włączyli kaplicę Golgoty do głównej budowli. Konsekracja nowej bazyliki odbyła się 50 lat po zdobyciu Jerozolimy – 15 lipca 1149. Na dziedzińcu powstał romański kościół, który łączył się z rotundą łukowym przejściem – pozostałością absydy z XI wieku.
W 1244 Jerozolima definitywnie przeszła w ręce muzułmanów – Chorezmijczyków będących na usługach egipskich Ajjubidów. Bazylika znów została znacznie uszkodzona, a wielu jerozolimskich chrześcijan wymordowanych. W 1246 r. sułtan As-Salih Ajjub przesłał na ręce papieża Innocentego IV przeprosiny. W ramach zadośćuczynienia mamelucy zapewnili dość znaczny dostęp do miejsc świętych dla chrześcijan. Aby nie wyróżniać żadnego z wyznań, klucze zostały powierzone muzułmanom i w formie znacznie łagodniejszej trwa tak do dzisiaj. Okres panowania mameluków stał się też początkiem powstawania zasad użytkowania poszczególnych kaplic i ołtarzy, ale także powstawania formalnych, lub nieformalnych placówek chrześcijan z Armenii, Grecji, Gruzji, Egiptu, Mezopotamii i Syrii.
W XVI wieku władzę nad całą Jerozolimą i Palestyną przejęli Turcy osmańscy. W tym czasie wyłączność na odprawianie nabożeństw przy Golgocie i edykule Grobu uzyskali prawosławni. Było to możliwe dzięki ich wpływom w Konstantynopolu. Niedługo po zdobyciu stolicy cesarstwa w 1453 sułtan Mehmed II Zdobywca ogłosił, że grecki patriarcha Jerozolimy będzie sprawował władzę zarówno religijną, jak i cywilną nad chrześcijanami zamieszkującymi tereny Imperium Osmańskiego. W miarę upływu czasu zdobywali coraz większą przewagę także nad pozostałymi wyznaniami chrześcijańskimi w Ziemi Świętej. Zyskiwali lepszy dostęp do sanktuariów, a ich duchowni sukcesywnie zajmowali stanowiska i funkcje w lokalnej hierarchii. Z czasem prawosławny patriarcha Jerozolimy był wyłaniany wyłącznie ze wspólnoty greckiej. W 1545 trzęsienie ziemi znów zniszczyło część bazyliki. Cesarz Karol V wraz z synem Filipem II Habsburgiem nakłonili więc papieża Juliusza III, by nakazał franciszkanom rozpoczęcie pilnego remontu. Cesarz przekazał potrzebne środki, a sułtan osmański Sulejman Wspaniały wydał firman akceptujący przebudowę. W 1757 sułtan Osman III wydał firman przyznający opiekę nad bazyliką Grobu Świętego, Grobem Marii Panny i bazyliką Bożego Narodzenia zdominowanemu przez Greków patriarchatowi Jerozolimy. Po pożarze bazyliki Grobu Świętego w 1808 naprawami i przebudową kierowali już prawosławni, co przypieczętowało ich dominację. W XIX wieku sprawa zwierzchności nad sanktuariami w Ziemi Świętej zaczęła przeradzać się w spór polityczny, w którym oponentami była opowiadająca się za prawami Kościoła łacińskiego Francja i optująca na rzecz prawosławnych Rosja. Od 1829 stały udział w dostępie do bazyliki Grobu Świętego uzyskał Apostolski Kościół Ormiański.
W lipcu 1927 Jerozolimę nawiedziło silne trzęsienie ziemi. Bazylika, zaniedbana i nie remontowana przez lata została poważnie uszkodzona[. Między innymi naruszona poważnie została konstrukcja grobowca i powstała groźba jego zawalenia. Tak poważne uszkodzenia zostały dostrzeżone jednak dopiero w 1933 przez brytyjskiego architekta Williama Harveya, który zalecił podparcie ścian rusztowaniem. Na przełomie lat 30. i 40. XX wieku łaciński patriarcha Jerozolimy, a zarazem kustosz Ziemi Świętej abp Alberto Gori prowadził konsultacje z przedstawicielami Francuskiej Szkoły Biblijnej i Archeologicznej w Jerozolimie oraz delegatem Watykanu, arcybiskupem Gustavo Testa w sprawie możliwej naprawy i przebudowy sanktuarium Grobu Świętego. Prace planistyczne zostały przerwane przez II wojnę światową. W drugiej połowie XX wieku trzy największe wspólnoty chrześcijańskie funkcjonujące w bazylice: grecka, ormiańska i łacińska, rozpoczęły realizację wspólnego projektu renowacji sanktuarium z równoczesnym przeprowadzeniem badań archeologicznych przy użyciu nowszych technik: w latach 1960–1969 kierował nimi profesor archeologii z Franciszkańskiego Studium Biblijnego w Jerozolimie Virgilio Corbo. W marcu 2016 przedstawiciele kościołów opiekujących się Bazyliką porozumieli się co do renowacji edykuły Grobu. Prace z udziałem około 50 ekspertów rozpoczęły się w maju, zaś 31 października tegoż roku odsłonięto płytę Grobu w którym miało spoczywać ciało Jezusa. Prace zakończyły się w marcu 2017 roku.
