Quando l’imperatore Costantino proclamò l’editto di Milano nel 313 d.C. che pose fine alle persecuzioni dei cristiani, fu deciso di erigere due importanti chiese nei luoghi di sepoltura dei due apostoli che trovarono la morte a Roma in seguito alla persecuzione neroniana: San Pietro nella necropoli vaticana e San Paolo nell’area dove oggi si trova la basilica di San Paolo Fuori le Mura, una necropoli che ancora si estende, sepolta, dalla basilica fino a quasi il fiume Tevere, appena fuori dalle Mura Aureliane, da tempo meta di pellegrinaggi. 
La prima chiesa di San Paolo, consacrata nel 324 da papa Silvestro, era più piccola dell’attuale a causa della posizione vicina al Tevere e alla necessità di orientare l’ingresso a est e l’abside – di cui si può notare la curva sul suolo della basilica attuale in seguito ai restauri del 2006 – conteneva il sepolcro del santo a cui era intitolata. L’afflusso sempre maggiore di pellegrini richiedeva però una struttura molto più grande e nel 385 si cominciò la costruzione di un nuovo edificio inglobando il precedente e cambiandone l’orientamento da est a ovest, per avere maggior spazio. Il modello era certamente la basilica costantiniana di San Pietro in Vaticano – non la basilica attuale, ma la prima costruzione di cui si è accennato all’inizio – in modo da poter dare anche a Paolo un riparo monumentale; del resto, secondo alcune attestazioni i due santi venivano onorati insieme sin da molto prima del 258. Il nuovo edificio, costruito come ex voto dei tre imperatori regnanti in quel momento (Teodosio, Arcadio e Onorio – o forse Valentiniano II, che pure morì nel 392, mentre Arcadio e Onorio furono associati al potere da Teodosio nel 393) senza badare a spese, fu consacrato nel 390 da papa Siricio e terminato circa nel 400.
Nel 1823, la basilica fu devastata da un incendio e il restauro successivo non rende giustizia a quello che doveva essere stata precedentemente; tuttavia, dimensioni e proporzioni sono sostanzialmente le stesse, come testimoniato da illustrazioni precedenti all’incendio.  Lunga 131,66 m, larga 65 m e alta 30 m, la basilica di San Paolo Fuori le Mura ha la pianta a croce latina ed è sviluppata in cinque navate suddivise da 80 colonne, un transetto continuo alto quasi quanto la navata centrale e separato da questa da un arco trionfale, con decorazione a mosaico che sopravvisse all’incendio, un’abside imponente. All’ingresso è presente un quadriportico realizzato tra il 1890 e il 1928, mentre il campanile, in stile neoclassico, fu ultimato nel 1860.
Alcuni scavi terminati nel 2009 hanno portato alla luce dei reperti archeologici tardomedievali, oggi visitabili.
La basilica di San Paolo Fuori le Mura è patrimonio dell’UNESCO dal 1980.