Zgodnie z tradycją wzdłuż Via Ostiense, pochowany został Apostoł narodów, pierwsi chrześcijanie zbudowali kaplicę grobową (cella memoriae), która później została przekształcona przez Konstantyna w bazylikę. Zawsze z tradycji bazylika była konsekrowana w 324 r. Przez papieża Sylwestra Pierwszego.

Rekonstrukcja mająca na celu powiększenie świątyni rozpoczęła się w 385 r. i zakończyła w 395 r. za czasów cesarza Honoriusza. Wkrótce stał się jednym z najważniejszych miejsc pielgrzymkowych do Rzymu.

Duża bazylika przedstawia trzy nawy ze starożytnymi kolumnami i czterdziestoma dwoma oknami oświetlającymi wnętrze. Gmina rozwinęła się wokół bazyliki z powodu najazdów Saracenów w IX wieku, a później została wzmocniona przez papieża Jana Ósmego, po czym nazwano ją Giovannopoli.

W ciągu wieków bazylika została wzbogacona wspaniałymi dziełami sztuki. Wspaniałe drzwi z brązu odlane w Konstantynopolu przez wykwalifikowanych robotników bizantyjskich zostały przekazane w 1070 r. Są nadal na miejscu, ale zwrócone do wewnątrz. Vassalletto, rodzina robotników z marmuru, działała w kościele w XIII wieku.

Aktywni byli również Arnolfo di Cambio, autor ciborium, i Pietro Cavallini, których dekoracje freskowe w nawie i mozaikowe dekoracje na fasadzie zostały niestety całkowicie utracone.

Kolejne interwencje zostały przeprowadzone w XV wieku (przez Benozzo Gozzoli i Antoniazzo Romano) i XVII wieku (przez Onorio Longhi i Carlo Maderno). Między 15 a 16 sierpnia 1823 roku bazylika została prawie zniszczona przez pożar, który oszczędził tylko transept i część fasady.

Komitet ustanowiony przez papieża Leona Dwunastego postanowił całkowicie odbudować świątynię po zbadaniu różnych rozwiązań. Pasquale Belli otrzymał zadanie wykonania robót i we współpracy z innymi architektami wyburzył pozostałe części i odbudował kościół, tak jak wygląda dzisiaj (1825-1854) według rozmiarów i planu starożytnej bazyliki.

Górny porządek fasady zdobią XIX-wieczne mozaiki autorstwa Luigiego Polettiego - który jest również autorem dzwonnicy i pronaos po stronie północnej. Pronaos został zbudowany z wykorzystaniem dwunastu kolumn, które były częścią nawy starożytnego kościoła - i jest poprzedzony dużym kwadriportico, zaprojektowanym pod koniec ubiegłego wieku przez Virgilio Vespignani.

W centrum czworoboku stoi posąg św. Pawła autorstwa Giuseppe Obici. Wnętrze podzielone jest na pięć naw przez osiemdziesiąt monolitycznych kolumn granitowych (sześć w holu wejściowym podarowanym przez wicekróla Egiptu Gregory'emu XVI jest wybitnych).

Większa nawa środkowa przedstawia mozaiki na ścianach z portretami papieży, które kontynuowane są także w nawach bocznych, oraz freski z historii życia św. Pawła. Łuk Triumfalny ozdobiony mozaikami z piątego wieku, niestety szeroko odrestaurowany, zamyka nawę główną.

Ołtarz główny zwieńczony jest słynnym gotyckim ciborium Arnolfo di Cambio (1285), składającym się z czterech czerwonych kolumn porfirowych, które podtrzymują dach ozdobiony rzeźbami w rogach i kolorowymi mozaikami. Po prawej stronie ołtarza znajduje się olbrzymi marmurowy świecznik do wielkanocnej świecy autorstwa Nicoli D'Angelo i Pietro Vassalletto z 1170 roku.

Apsyda jest zdominowana przez majestatyczną mozaikę zamówioną przez Innocentego Trzeciego (1198-1216) i zakończoną pod rządami Honoriusza Trzeciego (reprezentowanego w miniaturze u stóp Chrystusa błogosławionego i wśród świętych Piotra, Andrzeja, Pawła, i Lucas).

Na niższym poziomie odnajdujemy Apostołów, krzyżowany na krzyż Krzyż i Instrumenty Męki. Obszernie odrestaurowane fragmenty mozaik Cavalliniego, które zdobiły starożytną fasadę, trzymane są na zewnątrz absydy. Grobowiec Pietro Cavalliniego i dwa dzieła o wielkiej wartości, które szczęśliwie przetrwały pożar w 1823 r. (XIV-wieczny krucyfiks, przypisywany również Cavalliniemu i bardzo czczony drewniany pomnik św. Pawła z końca XIII w.) Są przechowywane w pobliskiej kaplicy Najświętszego Sakramentu, zaprojektowany przez Carlo Maderno, być może z pewnym wkładem młodego Borrominiego.

Transept daje dostęp do jednego z najpiękniejszych krużganków w Rzymie zbudowanego w XIII wieku przez Vassalletto z bogatymi i różnorodnymi małymi bliźniaczymi kolumnami podtrzymującymi małe łuki, które podtrzymują trabeację ozdobioną polichromatycznymi tarsiami i mozaikami.

Wiele fragmentów architektonicznych pochodzących ze starożytnej bazyliki i znalezisk archeologicznych z pobliskiego grobu Ostiense jest przechowywanych w klasztorze: szczególnie interesujący jest sarkofag Pietro Leone (XII wiek) ozdobiony scenami wyzwania i tortur Marsii