Есть данные, что ранние христиане, жившие в Иерусалиме, проводили литургические празднования около Гробницы Христа со времен Воскрешения, пока город не был взят римлянами в 66 году нашей эры. Меньше чем столетие спустя, в 135 году нашей эры, Император Андриан использовал камни с карьера около Гробницы, чтобы построить фундамент для храма Афродиты. Участок оставался погребенным под языческим храмом до времен Императора Константина Великого, принявшего Христианство в 312 году нашей эры. Новый император стал проявлять интерес к святым местам, связанным с его новой религией, и начал строить много церквей по всей Святой Земле. Строительство самой важной из них, Церкви Гроба Господнего, было начато в 326 году нашей эры. Строители Константина начали продалбливать склон горы таким образом, чтобы оставить высеченную из камня гробницу Христа отдельностоящей и построить церковь вокруг нее. Они также разрушили храм Андриана. В процессе строительства, согласно христианским историкам того времени, была найдена Скала Голгофы. Церковь была формально освящена в 335 году торжественной речью биографа Константина, Эвсебия Кесарийского.
В ходе раскопок мать Константина - Святая Елена, как полагают, обнаружила Истинный Крест около могилы. Она фактически обнаружила три креста - два креста, на которых были распяты воры, и один - на котором распяли Христа. Чтобы определить тот крест, на котором был распят Христос, к крестам подвели больного человека, и он должен был прикоснуться ко всем крестам, и к удивлению всех присутствующих от прикосновения к одному из крестов больной излечился, и именно этот крест посчитали крестом, на котором был распят Иисус. Церковь Константина - Гроба Господня была намного большей, чем та, которая стоит сегодня, но ее расположение не было изменено. Та первая церковь состояла из атриума (который снова использовался часть теменоса стены Андриана), покрытой базилики, открытого внутреннего двора с камнем Голгофы в юго-восточном углу, и гробницы Христа, которая располагалась в маленьком, круглом здании. Строительство храма Гроба Господнего не было закончено еще долгое время, поскольку требовалось большое количество рабочих для "срезания" горного утеса, чтобы изолировать гробницу; оно было закончено приблизительно 384 года нашей эры. Здание церкви было значительно повреждено пожаром в 614 году нашей эры, когда персы вторглись в Иерусалим. Они также захватили Истинный Крест, но в 630 году, Император Ираклий торжественно вошел в Иерусалим и вернул Крест на его место в восстановленной Церкви Гроба Господнего. Церковь была восстановлена при патриархе Модестусе без особых изменений к оригинальному плану. В 638 году, христиане были вынуждены сдать Иерусалим мусульманам под предводительством калифа Омара. В течение своего правления Иерусалимом Омар отказывался молиться в Церкви Гроба Господнего, говоря, "Если бы я молился в этой церкви, то она была бы потеряна для Вас {христиан}, а для моих сторонников [мусульман] это стало бы сигналом для преобразования ее в мечеть [ведь Омар молился здесь]". Однако у этого акта великодушия калифа были неприятные последствия для христиан. Церковь Гроба Господнего продолжала функционировать как христианская церковь под защитой Омара и ранних мусульманских правителей, но ситуация изменилась 18 октября 1009 года, когда "безумный" калиф Хаким Фатимид жестоко разрушил большую церковь.
Как ни странно, если бы Омар превратил церковь в мечеть, то Хаким оставил бы ее в покое. Но вместо этого, Хаким отдавал приказы разрушать церковь, сваливать стены, и приказал молотками разрушить гробницу Христа. Мусульмане остановились только тогда, когда развалины покрыли Гроб Господень. Восточные и западные стены были полностью разрушены, но северные и южные стены сохранились, вероятно, они были защищены щебнем от дальнейшего повреждения. Бедное христианское сообщество Иерусалима не могло позволить себе ремонт церкви, но в 1048 году Император Константин Мономах дал деньги для реконструкции. Однако халифат разрешил реконструкцию церкви только при условии соблюдения их условий: в частности, было запрещено восстанавливать церковь в тех же размерах, что и раньше, но стоит отметить, что халиф Хаким уничтожил большую часть той первой церкви Гроба Господнего. Атриум и базилика были полностью потеряны; только внутренний двор и ротонда частично сохранились. Последний был превращен в церковь с большой апсиды в фасаде. Восстановленная церковь была именно той церковью, к которой рыцари Первого Крестового похода прибыли, чтобы спеть свое Благодарственное письмо после завоевания Иерусалима 15 июля 1099 года. Руководитель крестоносцев Годфри Бульон, который стал первым королем Иерусалима, объявил себя Advocatus Sancti Sepulchri, что переводится, как "Защитник Гроба Господнего". Крестоносцы не спешили ремонтировать церковь, начиная делать модификации в романском стиле только в 1112 году. Они сначала построили монастырь с базиликой Константина, затем был выкопан Склеп Святой Елены. В 1119 году кувуклия (святыня) гроба Господнего была заменена. Коронация Фулка и Мелисинды в этой церкви состоялась в 1131 году и потребовала более радикальных архитектурных модификаций церкви. Внутренний двор Константина был занят романской церковью (освященной в 1149 году), которая была связана с ротондой большим арочным проходом, оставшимся от апсиды 11-ого столетия. В 1170 году была добавлена колокольня.
Три первичных хранителя церкви, назначенные, после прибытия крестоносцев в Иерусалим, были представителями Греческой Православной, Армянской Апостольской и Римо-католической церквей. В 19-ом столетии, представители Коптской Православной, Эфиопский Православной и Сирийской Православной церквей также стали хранителями Храма Гроба Господнего. В это время было составлено соглашение, которое регулирует время и "храмы" (часовни и другие церковные структуры, входящие в комплекс Гроба Господнего) для каждой Церкви.
Последующие столетия для Церкви Гроба Господнего также были разрушительными. Церковь страдала от повреждений, осквернений, и пренебрежения, и попыток ремонта (существенная реконструкция проводилась францисканцами в 1555 году, и в большей степени повредила церкви, чем восстановила). Пожар (1808 г.) и землетрясение (1927 г.) также привели к обширному повреждению зданий. Только в 1959 году представители трех главных сообществ (католики, православные и представители Армянской Апостольской церкви) договорились о главном плане реконструкции. Главный принцип реконструкции состоял в том, что только элементы, которые больше не могли выполнять свою структурную функцию, должны были быть заменены. Местные каменщики обучались обрезать камень в стиле 11-ого столетия для ротонды, и в стиле 12-ого столетия для церкви. Хаотичная история церкви очевидна в современном здании: византийские, средневековые элементы, элементы эпохи крестоносцев, и современные элементы присутствуют в церкви Гроба Господнего сегодня. Каждая христианская конфессия украсила свои святыни своим собственным отличительным способом.