324-ben építtette Nagy Konstantin császár, a Lateráni bazilika után néhány évvel.
A Pál apostol lábnyomait őrző számos római emlék közül megkülönböztetve, mint kiemelt
helyet kívánta létrehozni a Népek Apostola tiszteletére. A legrégebbi bizonyság
az Ostiába vezető úton található Szent Pál sírjáról a Cezáreai Eusebius Egyháztörténetében
olvasható. Eusebius egy 199 és 217 között írt szöveget idéz: „Meg tudom neked mutatni
az apostolok mártírhalálának helyét. Ha elmész a Vatikánba és az Ostiába vezető
útra, megtalálod az Egyház alapítóinak sírjait.” Ellentmondóak a Szent Pál római
mártírhalálának pontos körülményeire vonatkozó ismereteink. Kétségtelen, hogy Néró
császár üldözéseihez kapcsolódik vértanúsága. Azonban az 1823. július 15-16-ai éjszakán
kiütött tűz után, mely lerombolta a Szent Pál bazilikát, az újjáépítési munkálatok
folyamán előkerült régészeti bizonyítékok, azt tanúsítják, hogy a jelenleginél sokkal
kisebb Nagy Konstantin által építtetett bazilika kelet felé tájolt volt, amit 386-ban
a bazilikát kibővítő Valentianius, Nagy Theosodius és Arcadius császárok megváltoztattak.
A bazilika jelenlegi formáját végül Honorius császár alatt nyerte el. A bazilika környéke,
megépülése előtt a Kr. e. I. századtól a Kr. u. IV. századig városon kívüli mező volt,
melyet temetkezési helyként használtak. A hagyomány szerint Pál apostol testét
tanítványa, Timóteus és egy Lucina nevű római nemes asszony temette el, akinek a tulajdonába
tartozott az a földdarab. A 20. századi kutatások folyamán megtalált legfontosabb
lelet, az oltár alatt, Pál apostol sírján elhelyezett márványlap, melynek felirata:
Paulo Apostolo Mart(yri) vagyis „ a mártír Pál apostolnak”.