לפי המחקר הארכאולוגי, באזור בו עומדת כיום כנסיית הקבר פעלה כנראה עד תקופת הבית השני מחצבה. קונראד שיק מציין במחקרו הראשוני על הכנסייה את הימצאותה של מערת קבורה חצובה, מתוארכת לתקופת הבית הראשון, בסמוך לקיר הדרומי של הכנסייה. מערה זו כללה חלל שבקירותיו נחצבו מדפי קבורה. החלל נהרס כנראה בשלהי המאה ה-19, תוך כדי בניית בור מים במקום. שטח זה שכן, כאמור לעיל, מחוץ לחומות העיר ירושלים.
בתקופה הרומית, לאחר בניית "החומה השלישית", הוכלל השטח בתוך תחומי העיר. כחלק מבנייתה המחודשת של ירושלים כ"איליה קפיטולינה", הוקם בשטח זה ה"פורום" העירוני ובו מקדש לאלה אפרודיטי. על פי המסורת הנוצרית נהרס המקדש לאחר ביקורה של הלנה, אם הקיסר קונסטנטינוס, אחרי שהיא "גילתה את שרידי הצלב האמיתי" עליו נצלב ישו. אליבא דקואנון (Coüasnon), מבנה הבזיליקה של העיר שעמד בפורום זה, פורק ונבנה מחדש כבזיליקה של הכנסייה - (ה"מרטיריון") - בסמוך לסלע הצליבה, ולמבנה הקבר. הגם שאין הוכחות לטענה זו, היא התקבלה כסבירה על דעתם של חוקרים שונים.
עדות הקשורה לתקופה קודמת לבניית הכנסייה, התגלתה בחפירה ארכאולוגית בקפלת וארטן (St. Vartan): על אבן באורך 61 ס"מ, שנמצאה על קירותיו של מבנה רומי הקבור מתחת ליסודות הבזיליקה הקונסטנטינית (המרטיריון), משורטט רישום או "גרפיטי" של ספינת מסחר רומית, בפרופיל. מתחת לספינה מופיעה כתובת לטינית: "DOMINE IVIMUS" ("אלוהים, הלכנו" או "באנו"). על פי מגן ברושי הכתובת מאזכרת את הנוסח הלטיני של פסוק מספר תהילים קכ"ב: "שָׂמַחְתִּי בְּאֹמְרִים לִי; בֵּית ה' נֵלֵךְ", וכן של פסוק מן הבשורה על-פי יוחנן 6, 68 - "אֲדֹנִי אֶל־מִי נֵלֵךְ דִּבְרֵי חַיֵּי עוֹלָם עִמָּךְ".
התקופה הביזנטית.
בתחילת התקופה הביזנטית בארץ ישראל הוחל בבניית כנסייה לציון מקום צליבתו, קבורתו וקימתו לתחייה של ישו. מפעל בנייה נרחב זה החל בעקבות בקשתו של בישוף ירושלים מהקיסר בוועידת הכנסייה בניקאה, ב-325, לחשוף את קבר ישו. אדריכל הכנסייה, שנבנתה בין השנים 326–335, היה אמן ממוצא סורי או ארצישראלי, בשם זנוביוס. הכנסייה מוקמה על תוואי רחוב ה"קארדו", הנמתח משער שכם אל שער ציון. שורת מדרגות הובילו דרך שלושה פתחים לאטריום מלבני ממנו נכנסו המבקרים אל בזיליקה גדולה בעלת חמישה סטווים, גדולה כפליים מהכנסייה הנוכחית, בה נערכו טקסי הליטורגיה וטקסים אחרים. בצדה המערבי של הבזיליקה ניצב אפסיס גדול, מכוון מערבה אל מערת הקבר, ובו עמדו 12 עמודים, כמניין שנים-עשר השליחים של ישו. מהבזיליקה נכנסו המבקרים לחצר קטורה (ללא גג), שהייתה מוקפת בסטווים של עמודים, המכונה "הגן הקדוש", ובפינתה הדרום-מזרחית התנשא סלע הגולגולתא, שעוצב בעבודת חציבה. גבעה זו הייתה מקושטת ועמד עליה צלב מעוטר (Crux gemmata), תרומתו של הקיסר תיאודוסיוס השני. מן החצר נכנסו המבקרים ל"אנסטאזיס" (ביוונית: מקום התחייה) - אולם גדול ועגול הבנוי בצורת רוטונדה, במרכזו ניצב הקבר בתוך אדיקולה (היכלית). חלק זה נבנה, ככל הנראה, בשני שלבים: בתחילה היה קטור (חסר גג), ובשלב מאוחר יותר נוספה לו כיפה גדולה.
אוזביוס מקיסריה, שהיה מקורב לקיסר קונסטנטינוס, תיאר בחיבורו "חיי קונסטנטינוס" (Vita Constantini) את בניית הכנסייה על ידי הקיסר:
חפירה שנערכה בשטח הפטריארכיה הקופטית ב-1997, באזור שמצפון לכנסייה הנוכחית, חשפה שרידי מבנה ריבועי באורך 16 מטר העשוי מאבני גזית. המבנה תוארך למאות 4–5 לספירה והארכאולוגים מעריכים כי שימש כאחד ממבני הספח של הכנסייה, כגון בפטיסטריום, עליו היה ידוע מכתבי הצליינים.
לאורך התקופה הביזנטית שופץ המבנה מספר פעמים; את השיפוץ הנרחב ביותר ערך, כנראה, יוסטיניאנוס הראשון, קיסר האימפריה הביזנטית, במחצית השנייה של המאה ה-6. מבנה זה היה ללא ספק המבנה החשוב והמרכזי ביותר בירושלים באותה תקופה. עדות לכך ניתן למצוא ב"מפת מידבא" המתוארכת למאות 6–7 לספירה, שבה מוצגת כנסיית הקבר במרכז ירושלים.
עדות נוספת למרכזיותה של הכנסייה משתקפת בקביעת תאריך חג חנוכת הכנסייה ב-14 בספטמבר; תאריך החג הזה, שנחוג לראשונה ב-335, מציין גם את יום חנוכת מקדש יופיטר על גבעת הקפיטולין ברומא, וזה גם התאריך בו נחוג חג מציאת הצלב. בחירת התאריך ביום זה מסמל את ניצחונה של הנצרות על הפגניות. גם ייצוגים אמנותיים שונים מהתקופה מעידים על חשיבותה הדתית של הכנסייה: ייצוג כזה מופיע על גבי מיכלי שמן קדוש (אמפולות) ששימשו את עולי הרגל, ומצויים אף במבנים ממשיים, כדוגמת מבנה כנסיית סנטו סטפאנו רוטונדו (Santo Stefano Rotondo) ברומא, בהם הפך המבנה המרכזי המעוגל של הרוטונדה לאלמנט דתי סימבולי.
התקופה הפרסית והערבית הקדומה.
עם כיבוש ירושלים בידי הפרסים ב-614 נהרסה הכנסייה כמעט כליל, ונשארו ממנה רק שרידים דלים. הפרסים שהו בירושלים שנים ספורות, ועם שוב הביזנטים לירושלים ב-628 בראשותו של הקיסר הרקליוס עברה הכנסייה סדרת שיפוצים שלא הושלמו, שכן ב-638 כבשו המוסלמים את הארץ ופעולות הביזנטים בירושלים הוגבלו. עם זאת, המוסלמים לא נגעו לרעה בכנסייה, כחלק ממדיניות הסובלנות הכללית בה נהגו כלפי בני דתות אחרות שכבשו, במיוחד כלפי עמי הספר. מסופר אף כי כובש הארץ המוסלמי עומר בן אל-ח'טאב, סר לכנסייה לאחר כיבושה והתפלל בכבוד רב מול פתחה - ולא בתוכה, כדי שהכנסייה לא תהפוך לקדושה למוסלמים וייווצרו מריבות על שטחה. לפי סיפור זה, במקום בו התפלל עומר נבנה מסגד עומר, השוכן עד היום ליד כנסיית הקבר. סובלנות דומה לא אפיינה שליטים מוסלמים אחרים, ובשנת 1009 ציווה הח'ליפה הקנאי אל-חאכם באמר אללה להרוס את הכנסייה.
לפי עדותו של אולריך (Ulrich), בישוף העיר אורליאן על טקס "שבת האור", עדות המתוארכת בין השנים 1025–1028, בתקופה זו שוקם לכל הפחות מבנה האדיקולה. ב-1033 פקדה רעידת אדמה חזקה את ירושלים, בעטיה נהרסו מבנים רבים בעיר, ובהם מבנה כנסיית הקבר. בעקבות כך התירו הפאטימים (שליטי הארץ המוסלמים) לנוצרים לשקם את כנסייתם. הקיסר הביזנטי מונומכוס (Constantine IX Monomachos) ניצל היתר זה, ואחרי 1042 עברה הכנסייה שיפוץ יסודי ביוזמתו ובמימונו. בדיווח מ-1047 של מטייל פרסי בשם נאצר ח'וסרו (Nasir-i-Kusrau), מתוארת הכנסייה כמבנה מפואר "המסוגל להכיל קהל של 8,000 אנשים ... אשר נבנה במיומנות גבוהה ביותר, [בעזרת] שיש צבעוני, [מעוטר] באורנמנטיקה ופסלים...".
מתקופתו של מונומכוס נותרו שרידים בכנסייה. כנראה כבר בתקופתו נבנו שלוש הקפלות ממערב לחצר הכנסייה. אלה שייכות בשנות האלפיים ליוונים. בקשתות הבתולה ישנם עמודים מתקופתו, ובמספר מקומות מצויים שרידים של בנייה ביזנטית אופיינית לתקופה: לבנים דקות ובינן מילוי (למשל בקפלת אדם, או בכניסה לקתוליקון מהצד החיצוני). למעשה, המקום היחיד בו יש קפלה שהיא חיקוי של בניית מונומכוס - הוא הקפלה היוונית בדיר אברהם (המנזר היווני ממזרח לחצר הכנסייה).
התקופה הצלבנית והממלוכית.
ב-1099 כבשו הצלבנים את ירושלים לתקופה של 88 שנים, במהלכה הם שיפצו את הכנסייה, פיארו אותה אף יותר ממונומכוס, ולמעשה מבנה הכנסייה היום מושתת רובו ככולו על הבנייה הצלבנית מאז.
צליין אנגלו-סקסי בשם סאוולף (Saewulf), שביקר בארץ ישראל בין 1102–1103, מתאר בזיכרונותיו את הכנסייה: הרוטונדה, על פי תיאורו, הייתה בעלת גג פתוח או פתוח למחצה. סאוולף גם מציין בחיבורו מסורות שונות שנוצרו סביב חלל הכנסייה במשך מאות השנים, המצוינות באתרים שבתוך הכנסייה ומאזכרות אירועים שונים מחיי ישו - לדוגמה, תא המאסר של ישו, העמוד אליו נקשר ועונה, ועוד.
את הכנסייה המחודשת חנכה המלכה הצלבנית מליסנדה, בתו של בלדווין השני, ב-1149 - שנת היובל לכיבוש העיר בידי הצלבנים. כתובת שנחצבה בקשת באזור הגולגולתא מציינת את חנוכת הכנסייה ב-15 ביולי 1149: "מקום זה הוא קדוש, מקודש על ידי דמו של ישו. באמצעות הקידוש שלנו [את המקום] איננו מוסיפים דבר לקדושתו. אולם המבנה, אשר נבנה מסביב ומעל למקום קדוש זה, נוצר ביום החמישה עשר ביולי, בנוכחותם של אבות הכנסייה [ושל] הפטריארך פולקר (Fulcher), אשר היה אז בשנה הרביעית לכהונתו, השנה החמישים לכיבוש העיר, אשר אז קרנה כזהב טהור. מ[זמן] לידת אדוננו נספרו אלף מאה וארבעים ותשע שנים."
כנסיית הקבר הצלבנית הייתה קטנה בהרבה, וכללה בשטחה רק את חצר הגולגולתא ואת הרוטונדה. הצלבנים ויתרו למעשה על הבזיליקה הגדולה, אך קירו את הכנסייה כולה. גם כיוון הכניסה השתנה, ובמקום להיכנס ממזרח - החלו המבקרים להשתמש בכניסה חדשה מדרום, דרך חצר חיצונית. עם זאת, נוכחותו של שער כניסה צלבני ברחוב הנוצרים מעיד על כניסה לכנסייה ממערב שהתקיימה לפחות בין כיבוש ירושלים לבין חנוכת הכנסייה. צידו הפנימי של שער זה (המכונה גם "קשת מרים") נמצא באזור שבשליטת הפרנציסקנים.
משמאל לפתח הכניסה הוקם מגדל פעמונים ששרד רק בחלקו התחתון, ואילו מצד ימין נבנו מדרגות אל הגולגולתא. סביב האדיקולה הוקמה רוטונדה חדשה, בעלת אמבולטוריום המופרד בעזרת 18 עמודים מהחלל שמסביב הקבר. בכנסייה הוקמו אז גם קפלות שונות, שייצגו דמויות ואירועים מחיי ישו, וביקור בהן נחשב לביקור באתר "האמיתי". תיאור הכנסייה מופיע בכתבי יד שונים מן התקופה כמו מפת קמבריי, כשלצידה מכלול המסדר ההוספיטלרי.