La basilique Saint-Paul-hors-les-Murs fait partie des quatre basiliques majeures de Rome avec Saint-Jean-de-Latran, Sainte-Marie-Majeure et Saint-Pierre de Rome.
À sa mort, Paul est enterré dans une nécropole le long de la Via Ostiense, en dehors du Mur d'Aurélien (d'où le qualificatif « hors-les-Murs » associé au nom de l'édifice), au niveau de la Porta Ostiensis (ou "Porte Saint-Paul"). Avant l'Edit de Milan, il y avait déjà un culte secret rendu sur la tombe de Saint Paul. On y construit même un édicule (Cella Memoriae), comme sur la tombe de Saint Pierre.
Dès l'officialisation du Christianisme en 313, Constantin crée une basilique sur la tombe de Saint Paul, à environ 2 km de la muraille aurélienne qui ceinturait Rome. Ce premier édifice, occidenté, est consacré le 18 novembre 324 par le pape Sylvestre
A l’époque du règne de Théodose Ier, empereur d’Orient, il est remplacé par une basilique nouvelle, orientée cette fois, et également beaucoup plus vaste.
En 384, Valentinien II décide le début des travaux, comme en témoigne une lettre adressée par l’empereur au préfet de la ville de Rome, Sallustius, qui était chargé de l’étude des travaux.
Cet édifice est appelé Théodosina, et bien que terminé sous Honorius, il est construit par Cirade, dit "Professeur Mechanicus" qui projette le plan à cinq nefs et le portique à quatre arcades. L'édifice est consacré par le pape Sirice.
Galla Placidia, fille de Théodose, et épouse d'Honorius, fait ajouter la mosaïque de l'arc de triomphe, qui sera refaite entre le VIIIe siècle et le IXe siècle.
La basilique est ensuite saccagée par les Lombards, en 739, et par les Sarrasins en 847. Pour défendre le lieu saint, Jean VIII ordonna la construction d'un fortin, autour duquel se forma un bourg appelé Giovannipoli, dont il ne reste aujourd'hui plus aucune trace.
Au fil des siècles, les papes ont toujours embelli la basilique, par l'ajout de fresques, chapelles, plafond à caissons sur le transept,...
Sous le pontificat de Pie VII, dans la nuit du 15 au 16 juillet 1823, un incendie détruisit la majeure partie de l'édifice, mais le cloître ne fut pas endommagé. Léon XII s'occupa de la reconstruction de l'édifice. Il fut choisi de garder le plan paléochrétien et de construire un nouveau bâtiment.
Le projet de Giuseppe Valadier fut retenu par le Saint-Siège. Mais la Commission pour la reconstruction confia les travaux à Pasquale Belli. À sa mort Luigi Poletti lui succéda à la tête des travaux.
Le résultat final, bien qu'ayant gardé la typologie basilicale paléochrétienne, est loin de l'édifice de Théodose.
On boucha la moitié des fenêtres de la nef centrale pour ajouter 36 fresques représentant des épisodes de la vie de saint Paul et au dessous, une frise sur laquelle sont peints les papes de Pierre à Benoît XVI. On supprima toutes les irrégularités (colonnes torsadées, décors sous les arcades,...). On remplaça le pavement de marbre uniforme par un pavement géométrique. On plaça un plafond à caissons sur la nef centrale, masquant la charpente.
La mosaïque de la façade, du XIe siècle, fut remplacée par une nouvelle, loin des canons esthétiques paléochrétiens. Des restes de la première mosaïque sont visibles derrière l'arc de triomphe.
La basilique actuelle est ainsi un édifice néo-classique, style qui cherche ses références dans le Haut-Empire, témoin de son époque, et non plus un édifice paléochrétien, puisant dans l'art des derniers temps de l'Empire Romain.
L'intérieur de la basilique mesure 131.66 mètres de long, 65 mètres de large, 29.70 mètres de haut avec 80 colonnes monolithiques en granit de Montofarno. Il est divisé en cinq nefs.
Le portique réalisé par Calderini en 1928, mesure 70 mètres de long. Le pronaos de la façade compte dix colonnes monolithiques de granit rose de Baveno, une double rangée de colonnes sur les côtés, et une triple rangée du côté du Tibre, pour un total de 146 colonnes.
Le 31 mai 2005, le pape Benoît XVI ordonne que la basilique Saint-Paul-hors-les-Murs soit sous contrôle d'un cardinal archiprêtre comme les trois autres basiliques majeures.
Le premier cardinal archiprêtre en a été Andrea Cordero Lanza di Montezemolo.
