המסורת הנוצרית על המערה בה נולד ישו בבית לחם התגבשה ככל הנראה בשלב מוקדם מאוד ואולי אף הייתה מבוססת על מידע שעבר מדור לדור, זאת למרות שבתיאורי הברית החדשה ישו נולד באבוס ואין כלל התייחסות למערה. האזכור ההיסטורי הראשון למערה בה נולד ישו היה על ידי אוריגנס באמצע המאה השלישית. בחיבור “חיי קונסטנטינוס” אוזביוס מתאר אף הוא את המערה. הירונימוס, אשר עמד בראש מנזר גברים בבית לחם, קובע שבמערה בבית לחם התקיים פולחן ליופיטר, לוֶונוּס ולאדוֹניס. מקורות אחדים קובעים שפולחן האלים במערה החל בימי הדריאנוס קיסר, בראשית המאה השנייה לספירה, והוא נועד לבזות את המאמינים בישו.
רק לאחר שקונסטנטינוס הגדול קבע את הנצרות כדת רשמית באימפריה ולאחר ועידת ניקאה, יזם הבישוף של ירושלים את הקמת כנסיית המולד בתמיכתה של הלנה, אמו של הקיסר. כנסיית המולד נבנתה בכדי לשרת שתי מטרות מרכזיות: אתר הנצחה למערה ולאבוס שם נולד ישו ומקום בו ניתן היה לכנס קהל מאמינים רחב לתפילה ולטקסים ליטורגיים. בתקופה הביזנטית הנוהג היה לתכנן ולבנות מבנים הֶרְכֶּזִיים לשם הנצחה. המיוחד במבנים אלה היה בכך שנקודת הציון ההיסטורית היוותה המרכז הגיאומטרי של המבנה אשר הוקם בתכנית מעגל או פוליגון רב צלעות מסביב לנקודה. זאת בניגוד לכנסייה הבסיליקלית עצמה אשר הייתה בעלת ציר אורך בכיוון מערב-מזרח. בהתאם לכך, הוקמה כנסיית הקבר כבסיליקה, אשר במערבה אטריום – חצר קטורה (לא מקורה) המוקפת בסטווים מקורים הנתמכים בידי טורי עמודים הסובבים את החצר. הצלע המזרחית של החצר הוליכה לשלושה פתחים מרשימים, המרכזי ביניהם היה גדול משני הפתחים האגפיים והוא הוביל אל אולם התווך של הכנסייה, בעוד שני הפתחים האגפיים הובילו, כל אחד מהם, לשתי סיטראות. במזרחה של הבסיליקה הייתה במה מוגבהת ומעבר לה נבנה מעל המערה מבנה אוקטגונאלי, בעל שמונה צלעות שוות ובתוכו היו שני גרמי מדרגות שאפשרו כניסה ויציאה של מאמינים רבים שביקשו לבקר במערה.
הבסיליקה הייתה מרוצפת בפסיפסים ופסיפסים נוספים עיטרו גם את קירות הכנסייה ולצדם שובצו לוחות שיש עליהם דגמים מרשימים. יש הרואים את מקורות הבסיליקה הנוצרית בבסיליקה האזרחית שהוקמה בערים רומיות רבות. יתכן שגם בתי הכנסת הקדומים אשר הוקמו דורות אחדים קודם לכן היוו מקור השראה לכנסיות. התכנית של הכנסיות הראשונות, בהן גם כנסיית הקבר בירושלים וכנסיית העלייה לשמיים בהר הזיתים, נותרה על כנה מראשיתה ועד ימינו והיא השפיעה מאוד גם על אדריכלות המסגדים בעולם האסלם. אך לאחר מאות שנים אחדות מיעטו הנוצרים לבנות מבנים הרכזיים במזרח הבסיליקה ואת מקומם החליף אפסיס במתאר חצי עגול.
אף שכבר במאה הרביעית לספירה החלה להתפתח תנועת נזירות בבית לחם, לצד כנסיית המולד, בית לחם עצמה נותרה כפר קטן או לכל היותר עיירה קטנה אשר התקשתה מאוד לספק את צרכיהם של עולי רגל רבים שפקדו אותה.
בשנת 539 לספירה, בימי הקיסר יוסטיניאנוס, נהרסה הכנסייה, ככל הנראה בעקבות אירועי המרד השומרוני ובמקומה החלו בבניית כנסייה חדשה. משלחת החפירות שפעלה בכנסייה בשנות ה-30 של המאה העשרים הגיע למסקנה שמרבית מבנה הכנסייה הקיים הוקם במאה השישית ושרד עד ימינו, כולל קורות עץ ששולבו במבנה. על פי ממצאי המשלחת עולה שהכנסייה מימי קונסטנטינוס חרבה עד ליסוד ועל יסודותיה נבנה מבנה חדש.
את האוקטגונל שמעל למערה החליף אפסיס ראשי ואפסיסים משניים מצדיו. על פי מסורת שתועדה על ידי אאוטיכיוס, הפטריארך של אלכסנדריה במאה התשיעית, הקיסר יוסטיניאנוס ציווה לכרות את ראשו של אדריכל הכנסייה. לא ברור מה הייתה הסיבה לגורלו של האדריכל, אך קיימת סברה לפיה האדריכל ביקש להקים מבנה כיפתי מעל המערה, אך בשל קוטרו, 33 מטרים, הוא לא הצליח לבסס את הכיפה ולפיכך הוחלט לאמץ את תכנית האפסיס. רצפתה של הכנסייה החדשה הוקמה כמה עשרות סנטימטרים מעל לרצפה בת המאה הרביעית ובחפירות בדיקה שבוצעו תחת הרצפות נמצאו הפסיפסים של הרצפה המקורית.
הכנסייה בת המאה השישית עוטרה בפסיפסים עשירים בטֶסֶרוֹת (קוביות פסיפס), בהן רבות מוזהבות. הרצפה רוצפה בלוחות שיש. בכדי לאפשר תפילה סדורה בבסיליקה בחרו להקים שתי כניסות עצמאיות למערה וכך זרם המבקרים במקום לא פגע בהתנהלות בכנסייה.
בראשית המאה השביעית תקפו הפרסים את האימפריה הביזנטית והחריבו כנסיות רבות בתחומה. מסורת מהמאה התשיעית מספרת שהלנה, אמו של קונסטנטינוס, ציוותה להקים פסיפס מפואר על הקיר המערבי של הכנסייה בו היה תיאור של מסורת נוצרית המוזכרת בבשורה על פי מתי, על ביקור של האמגושים – כהני דת ממדי שבפרס, את ישו התינוק שנולד בבית לחם. על פי המסורת, בשל הופעתם של האמגושים בפסיפס, נמנעו הפרסים מלהרוס את הכנסייה.
כשהחל הכיבוש הצלבני של הארץ, בשנת 1099, המוסלמים פגעו בכנסיות רבות ובקהילות נוצריות ברחבי הארץ. וילהלם מצור מעיד שאנשי בית לחם שלחו משלחת לאמאוס, שם שהה גוטפריד מבויון, בראש הצבא הצלבני. הם ביקשו ממנו להחיש חיל משמר מיומן לבית לחם בטרם המוסלמים יפגעו בכנסיית המולד. גוטפריד בחר בטנקרד לפקד על כוח של מאה פרשים אשר הגיעו לבית לחם עם שחר והגנו עליה. כאשר בלדווין הוכרז כמלך ממלכת ירושלים הצלבנית הוא בחר לבצע את טקס ההכתרה בכנסיית המולד בבית לחם, זאת משני טעמים: ראשית, הוא לא רצה להכתיר את עצמו בכתר זהב במקום בו ישו הושפל עד מותו בירושלים. שנית, יש הסוברים שהוא רצה שמקום הכתרתו יהיה בעירו של דוד המלך, והטקס נערך בחג המולד של שנת 1101. בלדווין דרש להפוך את בית לחם למושב אפיסקופלי (בו יושב בישופ) והחל משנת 1110 הפכה כנסיית המולד לקתדרלה. עשרים שנים לאחר מכן גם המלך בלדווין ה-2 הוכתר
בכנסיית המולד. הצלבנים העניקו נכסים רבים לכנסייה ובכך סייעו לגייס משאבים לשיקומה, לאחר מאות שנים של הזנחה תחת השלטון המוסלמי. את השיקום ניהל אומן אנגלי בשם ראול, אשר שמו הונצח בפסיפסים רבים שהותקנו בתקופה זו בכנסייה. אך על פי הסגנון האמנותי של עבודות השיקום ניכר שעיקר האמנים היו מקומיים. במסגרת עבודות השיקום הוחלפו הגמלונים שמעל פתחי הכניסה והוצבו בכניסות עמודים ובראשם כותרות צלבניות, אשר נותרו במקומם עד ימינו. גם גג הכנסייה הוחלף בתקופה זו. הצלבנים בנו מבנים נלווים לכנסייה, הבולט בהם היה מגדל הפעמונים.
עם הכיבוש הממלוכי, גורשו הנוצרים מבית לחם לתקופה ממושכת. חלק מהקהילות הנוצריות הורשו לחזור לעיר ולכנסייה תחת השלטון העות’מני, אך השליטים העות’מנים מנעו מהנוצרים לתחזק את הכנסייה והם התירו לבזוז חלקים ממנה ומהמבנים הסמוכים לה כחומרי גלם לבנייה בירושלים. בנסיבות אלה פורק גג הכנסייה בשנת 1670, ונלקחה ממנו עופרת לצורך הכנת תחמושת. בשלהי המאה השבע-עשרה שוקם הגג על ידי היוונים האורתודוכסים, אשר הביאו קורות ענק מאיסטנבול לשם כך. נדרשו חמישה חודשים להוביל את הקורות באמצעות ארבעה שוורים מנמל יפו לבית לחם. מבצע ההובלה המורכב חייב לשפץ קטעים מהדרך לצורך מעבר השיירה.
