bazilica a fost fondată de împăratul Roman Constantin I peste locul de înmormântare al Sfântului Pavel, Unde s-a spus că, după executarea Apostolului, adepții săi au ridicat un memorial, numit cella memoriae. Această primă bazilică a fost sfințită de Papa Silvestru în 324.
în 386, împăratul Teodosie I a început să ridice o bazilică mult mai mare și mai frumoasă, cu naos și patru culoare cu transept. A fost sfințită probabil în jurul anului 402 de Papa Inocențiu I. Lucrarea, inclusiv mozaicurile, nu a fost finalizată până la pontificatul lui Leon I (440-461). În secolul al 5-lea a fost mai mare decât Bazilica Sfântul Petru vechi. Poetul creștin Prudentius, care l-a văzut pe vremea împăratului Honorius (395-423), descrie splendorile monumentului în câteva rânduri expresive.
sub Leul I, lucrări de reparații extinse au fost efectuate în urma prăbușirii acoperișului din cauza focului sau a fulgerului. În special, transeptul (adică zona din jurul mormântului lui Pavel) a fost ridicat și un nou altar principal și presbiteriu instalat. Aceasta a fost probabil prima dată când un altar a fost așezat deasupra mormântului Sfântului Paul, care a rămas neatins, dar în mare parte subteran, având în vedere nivelurile nou ridicate ale etajului lui Leo. Leo a fost, de asemenea, responsabil pentru fixarea arcului de Triumf și pentru restaurarea unei fântâni în curte (atrium). sub Papa Grigorie cel Mare (590-604) altarul principal și presbiteriul au fost modificate pe larg. Pavajul din transept a fost ridicat și un nou altar a fost așezat deasupra altarului anterior ridicat de Leon I. poziția era direct peste sarcofagul Sfântului Paul.
în acea perioadă existau două mănăstiri lângă bazilică: Sfântul Aristus pentru bărbați și Sfântul Stefano pentru femei. Liturghiile au fost celebrate de un corp special de clerici instituit de Papa Simplicius. De-a lungul timpului, mănăstirile și clerul bazilicii au scăzut; Papa Sfântul Grigorie al II-lea l-a restaurat pe primul și le-a încredințat călugărilor grija bazilicii.pe măsură ce se afla în afara zidurilor Aureliene, bazilica a fost deteriorată în secolul al 9-lea în timpul unui raid Sarazin. În consecință, Papa Ioan al VIII-lea (872-82) a fortificat Bazilica, mănăstirea și locuințele țărănimii, formând orașul Johannispolis (italiană: Giovannipoli) care a existat până în 1348, când un cutremur a distrus-o în totalitate.în 937, când Sfântul Odo de Cluny a venit la Roma, Alberic al II-lea de Spoleto, Patrician al Romei, a încredințat mănăstirea și Bazilica congregației sale, iar Odo l-a pus la conducere pe Balduino de Monte Cassino. Papa Grigore al VII-lea a fost stareț al mănăstirii și în timpul său Pantaleone, un negustor bogat din Amalfi care locuia la Constantinopol, a prezentat ușile de bronz ale bazilicii maior, care au fost executate de artiștii Constantinopolitani; ușile sunt inscripționate cu rugăciunea lui Pantaleone pentru ca „ușile vieții” să-i fie deschise. Papa Martin al V-lea a încredințat-o călugărilor Congregației din Monte Cassino. Apoi a fost făcută o abație nullius. Jurisdicția starețului s-a extins asupra districtelor Civitella San Paolo, Leprignano și Nazzano, toate formând parohii.
grațioasa mănăstire a mănăstirii a fost ridicată între 1220 și 1241.
Din 1215 până în 1964 a fost sediul Patriarhului latin al Alexandriei.
la 15 iulie 1823, un muncitor care repara plumbul acoperișului a declanșat un incendiu care a dus la distrugerea aproape totală a acestei bazilici, care, singură dintre toate Bisericile Romei, și-a păstrat o mare parte din caracterul său original timp de 1435 de ani.
în 1825, Leon al XII-lea a emis enciclica ad plurimas încurajând donațiile pentru Reconstrucție. Câteva luni mai târziu, el a emis ordine ca Bazilica să fie reconstruită exact așa cum fusese când era nouă în secolul al IV-lea, deși a stipulat, de asemenea, că elemente prețioase din perioadele ulterioare, cum ar fi mozaicurile medievale și tabernacolul, să fie, de asemenea, reparate și păstrate. Aceste linii directoare s-au dovedit nerealiste din mai multe motive și au încetat în curând să fie puse în aplicare. Rezultatul este o bazilică reconstruită care are doar o asemănare generală cu originalul și nu este în niciun caz identică cu aceasta. Reconstrucția a fost încredințată inițial arhitectului Pasquale Belli, care a fost succedat la moartea sa în 1833 de Luigi Poletti, care a supravegheat proiectul până la moartea sa în 1869 și a fost responsabil pentru partea leului din lucrare. Multe elemente care au supraviețuit incendiului au fost refolosite în reconstrucție. Mulți conducători străini au adus, de asemenea, contribuții. Muhammad Ali Pașa, vicerege al Egiptului a dat coloane de alabastru, în timp ce împăratul Rusiei a donat prețioase malachit și lapis lazuli care a fost folosit pe unele dintre fronturile altarului. Transeptul și altarul înalt au fost consacrate în 1840 și acea parte a bazilicii a fost apoi redeschisă. Întreaga clădire a fost reconsacrată în 1854 în prezența Papei Pius al IX-lea și a cincizeci de cardinali. Cu toate acestea, multe caracteristici ale clădirii erau încă executate la acea dată, iar lucrările s-au extins în cele din urmă în secolul al XX-lea. Quadriporticus privind spre Tibru a fost completat de Guvernul Italian, care a declarat Biserica monument național. La 23 aprilie 1891, o explozie la revista gunpowder de la Forte Portuense a distrus vitraliile bazilicii.
la 31 mai 2005 Papa Benedict al XVI-lea a ordonat ca Bazilica să intre sub controlul unui Protopop și l-a numit pe Arhiepiscopul Andrea Cordero Lanza di Montezemolo drept primul său Protopop.