basilikan grundades av den romerska kejsaren Konstantin i över gravplatsen för Saint Paul, där det sägs att efter apostelens avrättning uppförde hans anhängare ett minnesmärke, kallat en cella memoriae. Denna första basilika invigdes av påven Sylvester år 324.
år 386 började kejsaren Theodosius I bygga en mycket större och vackrare basilika med ett skepp och fyra gångar med ett transept. Det invigdes förmodligen runt 402 av påven Innocent I. Verket, inklusive mosaikerna, slutfördes inte förrän Leo I: s pontifikat (440-461). På 5: e århundradet var det större än den gamla Peterskyrkan. Den kristna poeten Prudentius, som såg den vid tiden för kejsaren Honorius (395-423), beskriver monumentets prakt i några uttrycksfulla linjer.
under Leo I utfördes omfattande reparationsarbeten efter takets kollaps på grund av eld eller blixtnedslag. I synnerhet transeptet (dvs. området runt Paulus grav) höjdes och ett nytt huvudaltare och prästerskap installerades. Detta var förmodligen första gången som ett altare placerades över Saint Pauls grav, som förblev orörd, men till stor del underjordiskt med tanke på Leos nyligen förhöjda golvnivåer. Leo var också ansvarig för att fixa Triumfbågen och för att återställa en fontän på gården (atrium).
under påven Saint Gregorius den store (590-604) modifierades huvudaltaret och prästgården i stor utsträckning. Trottoaren i transeptet höjdes och ett nytt altare placerades ovanför det tidigare altaret uppfört av Leo I. positionen var direkt över Saint Pauls sarkofag.
under den perioden fanns det två kloster nära basilikan: Saint Aristus för män och Saint Stefano för kvinnor. Massorna firades av en särskild grupp präster som inrättades av påven Simplicius. Med tiden klostren och basilikan präster minskade; påven Saint Gregorius II återställde den förra och anförtrott munkarna med basilikan vård.
När det låg utanför Aurelian väggar, basilikan skadades i den 9: e århundradet under en Saracen raid. Följaktligen befäste påven Johannes VIII (872-82) basilikan, klostret och böndernas bostäder och bildade staden Johannipolis (italienska: Giovannipoli) som fanns fram till 1348, då en jordbävning helt förstörde den.
år 937, när Saint Odo av Cluny kom till Rom, anförde Alberic II av Spoleto, patricier i Rom, klostret och basilikan till sin församling och Odo placerade Balduino av Monte Cassino ansvarig. Påven Gregorius VII var abbot i klostret och i sin tid Pantaleone, en rik köpman av Amalfi som bodde i Konstantinopel, presenterade bronsdörrarna till basilica maior, som utfördes av Konstantinopolitiska konstnärer; dörrarna är inskrivna med Pantaleones bön att ”livets dörrar” kan öppnas för honom. Påven Martin V anförtrodde det till munkarna i församlingen Monte Cassino. Det gjordes sedan ett kloster nullius. Abbotens jurisdiktion sträckte sig över distrikten Civitella San Paolo, Leprignano och Nazzano, som alla bildade församlingar.
klostrets graciösa kloster uppfördes mellan 1220 och 1241.
från 1215 till 1964 var det säte för den latinska patriarken i Alexandria.
den 15 juli 1823 startade en arbetare som reparerade takets ledning en eld som ledde till den nästan totala förstörelsen av denna basilika, som ensam bland alla kyrkor i Rom hade bevarat mycket av sin ursprungliga karaktär i 1435 år.
år 1825 utfärdade Leo XII encyklikan ad plurimas uppmuntrande donationer för återuppbyggnaden. Några månader senare utfärdade han order om att basilikan skulle byggas om exakt som den hade varit när den var ny under det fjärde århundradet, även om han också föreskrev att värdefulla element från senare perioder, såsom medeltida mosaiker och tabernakel, också repareras och behålls. Dessa riktlinjer visade sig vara orealistiska av olika skäl och upphörde snart att verkställas. Resultatet är en rekonstruerad basilika som bara har en allmän likhet med originalet och inte alls är identisk med den. Rekonstruktionen anförtrotts ursprungligen arkitekten Pasquale Belli, som efterträddes vid hans död 1833 av Luigi Poletti, som övervakade projektet fram till sin död 1869 och var ansvarig för lejonens andel av arbetet. Många element som hade överlevt branden återanvändes i återuppbyggnaden. Många utländska härskare gjorde också bidrag. Muhammad Ali Pasha, Egyptens Viceroy gav kolonner av alabaster, medan Rysslands kejsare donerade dyrbar malakit och lapis lazuli som användes på några av altarfronterna. Transept och högaltar invigdes 1840 och den delen av basilikan öppnades sedan igen. Hela byggnaden rekonstruerades 1854 i närvaro av påven Pius IX och femtio kardinaler. Många funktioner i byggnaden var fortfarande att utföras vid det datumet, dock, och arbetet slutligen utvidgas till det tjugonde århundradet. Quadriporticus som tittade mot Tibern slutfördes av den italienska regeringen, som förklarade kyrkan som ett nationellt monument. Den 23 April 1891 förstörde en explosion vid krutmagasinet i Forte Portuense basilikans glasmålningar.
den 31 maj 2005 påven Benedictus XVI beordrade basilikan att komma under kontroll av en ärkeprest och han namngav ärkebiskop Andrea Cordero Lanza di Montezemolo som sin första ärkeprest.