Le long de la Via Ostiense à l'endroit où était traditionnellement enterré l'apôtre des peuples, les premiers chrétiens ont construit une chapelle funéraire (cella memoriae) qui a ensuite été transformée en basilique par Constantine. Toujours selon la tradition, la basilique a été consacrée en 324 par le pape Sylvestre Premier.

La reconstruction pour agrandir le temple fut commencée en 385 et achevée en 395 à l'époque de l'empereur Honorius. Il est rapidement devenu l’une des étapes les plus importantes des pèlerinages à Rome.

La grande basilique présente trois nefs avec des colonnes anciennes et quarante-deux fenêtres éclairant l'intérieur. Un bourg s'est développé autour de la basilique suite aux raids sarrasins du IXe siècle et a été fortifié plus tard par le pape Jean Huitième, après lequel il s'appelait Giovannopoli.

Au fil des siècles, la basilique s'est enrichie de magnifiques œuvres d'art. Les magnifiques portes de bronze moulées à Constantinople par des ouvriers qualifiés de Byzantins ont été données en 1070. Elles sont toujours in situ, mais tournées vers l’intérieur. Les Vassalletto, une famille de marbriers, étaient actifs dans l'église au XIIIe siècle.

Arnolfo di Cambio, auteur du ciboire, et Pietro Cavallini, dont les décorations de fresques dans la nef et les décorations en mosaïque sur la façade ont également été totalement perdues.

D'autres interventions ont été effectuées au XVe siècle (par Benozzo Gozzoli et Antoniazzo Romano) et au XVIIe siècle (par Onorio Longhi et Carlo Maderno). Entre le 15 et le 16 août 1823, la basilique est presque détruite par un incendie qui n'épargne que le transept et une partie de la façade.

Le comité institué par le pape Léon XII a décidé de reconstruire complètement le temple après avoir examiné différentes solutions. Pasquale Belli s'est vu confier la tâche de réaliser les travaux. En collaboration avec d'autres architectes, il a démoli les parties restantes et a reconstruit l'église telle qu'elle se présente aujourd'hui (1825-1854) en respectant les dimensions et le plan de l'ancienne basilique.

La partie supérieure de la façade est décorée de mosaïques du XIXe siècle de Luigi Poletti - qui est aussi l'auteur du clocher et du pronaos du côté nord. Le pronaos a été construit en réutilisant douze colonnes qui faisaient partie de la nef de l'ancienne église. Il est précédé d'un grand quadriportique conçu à la fin du siècle dernier par Virgilio Vespignani.

Au centre du quadriportico se trouve la statue de Saint Paul de Giuseppe Obici. L'intérieur est divisé en cinq nefs par quatre-vingts colonnes monolithiques en granit (les six dans le hall d'entrée offert par le vice-roi d'Égypte à Grégoire XVI sont remarquables).

La grande nef centrale présente sur les murs des mosaïques avec des portraits de papes qui continuent également dans les nefs latérales, ainsi que des fresques de l'histoire de la vie de Saint Paul. L'arc de triomphe orné de mosaïques du Ve siècle, malheureusement largement restaurées, ferme la nef centrale.

Le maître-autel est surmonté du célèbre ciboire gothique d'Arnolfo di Cambio (1285), composé de quatre colonnes de porphyre rouge qui supportent le toit orné de statues aux coins et de mosaïques colorées. Un chandelier en marbre pour la bougie de Pâques faite par Nicola D’Angelo et Pietro Vassalletto en 1170 est placé à droite de l’autel.

L'abside est dominée par la majestueuse mosaïque commandée par Innocent III (1198-1216) et terminée sous Honorius III (représentée en miniature aux pieds du Christ bénédictif et parmi les saints Pierre, André, Paul, et Lucas).

Dans le niveau inférieur, nous trouvons les apôtres, une croix et des instruments de passion. Des fragments de mosaïques de Cavallini, qui ont décoré l'ancienne façade et qui ont été largement restaurés, sont conservés à l'extérieur de l'abside. La tombe de Pietro Cavallini et deux œuvres de grande valeur ayant survécu à l'incendie de 1823 (un crucifix du XIVe siècle, également attribué à Cavallini, et une statue très vénérée de Saint Paul en bois datant du XIIIe siècle) sont conservées dans la chapelle voisine. du Saint Sacrement, conçu par Carlo Maderno, peut-être avec l’aide du jeune Borromini.

Le transept donne accès à l'un des plus beaux cloîtres de Rome construit au XIIIe siècle par Vassalletto avec de petites colonnes jumelles riches et bigarrées soutenant de petites arches, supportant une trabéation décorée de tarsias et de mosaïques polychromes.

De nombreux fragments architecturaux provenant de l'ancienne basilique et des découvertes archéologiques du cimetière d'Ostiense situé à proximité sont conservés dans le cloître: le sarcophage de Pietro Leone (XIIe siècle) revêt un intérêt particulier. Il est décoré de scènes du défi et de torture. de Marsia