המבנה הראשוני שהוקם על ידי קונסטנטינוס בתחילת המאה ה-4, הורחב תחת שלטונו של ולנטיניאנוס הראשון במחצית השנייה של המאה. בשנת 386 הקיסר תאודוסיוס הראשון החל בבניית בזיליקה גדולה ומפוארת יותר, שבה ספינה ראשית, ארבע ספינות משניות וטרנספט. ההקמה הושלמה רק בתקופת כהונתו של לאו הראשון. במאה ה-5 הייתה הבזיליקה גדולה גם מבזיליקת פטרוס הקדוש, והמשורר הנוצרי פרודנטיוס (אנ'), שראה אותה בתקופתו של הקיסר הונוריוס, תיאר את יופייה בשורות בודדות ותמציתיות. כיוון שהבזיליקה הוקדשה גם לקדושים טאורינוס והרקולאנוס, מרטירים מחבל אוסטיה במאה ה-5, היא נקראה גם "בזיליקת טריום דומינורום" (basilica trium Dominorum - בזיליקת שלושת האדונים).

בתקופתו של גרגוריוס הראשון (590 – 604) הורחבה הבזיליקה פעם נוספת. הרצפה הוגבהה על מנת שהמזבח יהיה בדיוק מעל לקברו של פאולוס. רק מי שהתוודה היה רשאי לגשת אל הקבר. כיוון שהבזיליקה הייתה מחוץ לחומות האורליאניות, היא ספגה נזקים במהלך פלישות הסרצנים במאה ה-9. בתגובה לכך האפיפיור יוחנן השמיני ביצר את הבזיליקה, המנזר ואת בתי המגורים של האיכרים, ובכך יצר את העיר יוחנניספוליס (באיטלקית: Giovannipoli - ג'יובניפולי). העיר התקיימה עד שנת 1348, מועד בו נחרבה לחלוטין ברעידת אדמה.

בשנת 937 כאשר הקדוש אודו מקליני הגיע לרומא, השליט הרומאי אלבריק השני מספולטו הפקיד את המנזר והבזיליקה בידי אודו, וזה מינה את בלדווינו ממונטה קאסינו לאחראי עליה. האפיפיור גרגוריוס השלישי היה ראש המנזר לפני שהתמנה לאפיפיור, ובתקופתו פנטלאונה מאמאלפי הביא את דלתות הארד של הבזיליקה הגדולה, שנבנו על ידי אומנים מקונסטנטינופול. האפיפיור מרטינוס החמישי הפקיד את הבזיליקה בידי הנזירים של קהילה מונטה קאסינו והיא הפכה למקום המושב של ראש המנזר האזורי. הקלויסטר של המנזר נבנה בין שנת 1220 לשנת 1241.

ב-15 ביולי 1823 פרצה שרפה בעקבות רשלנות של עובדים שתיקנו את העופרת שבגג המבנה, ובעקבותיה נהרס רובו. הבזיליקה הייתה הכנסייה היחידה ברומא ששמרה על צורתה הקדומה במשך 1435 שנות קיומה, ומאמינים רבים מכל רחבי העולם תרמו כספים לשיקומה. המשנה למלך של מצרים שלח עמודי אלבסטר והצאר הרוסי תרם חומרי בנייה יקרים כמו מלכיט ולפיס לזולי. העבודה על החזית העיקרית, שפנתה לכיוון נהר הטיבר, הושלמה על ידי ממשלת איטליה שהכריזה על האתר כעל אוצר לאומי.

הבזיליקה נחנכה מחדש בשנת 1840, אולם היא קודשה רק חמש-עשרה שנים לאחר מכן בנוכחות האפיפיור פיוס התשיעי וחמישים קרדינלים. ב-23 באפריל 1891 נהרסו הזכוכיות הצבועות בבזיליקה בעקבות פיצוץ.

ב-31 במאי 2005 האפיפיור בנדיקטוס השישה עשר קבע כי הכנסייה תופקד באחריותו של כומר ראשי, ובו ביום הוא מינה את הארכיבישוף אנדראה קורדרו לאנצה די מונטצלמו למשרה.