Com o fim das perseguições e a promulgação dos editos de tolerância ao cristianismo, no início do século IV, o imperador Constantino ordenou escavações nos lugares da cella memoriae, onde os cristãos veneravam a memória do apóstolo São Paulo, decapitado entre 65 e 67, sob o império de Nero. Foi sobre esse túmulo, situado na via Ostiense, aproximadamente 2 km fora dos muros aurelianos que cercam Roma, que mandou erguer uma Basílica, consagrada pelo papa Silvestre em 324.

Reformada e ampliada entre 384 e 395, sob os impérios de Teodósio, Valentino II e Arcádio, e disposta num amplo plano em cinco naves instalado além de um pórtico de quatro faces, a Basílica não cessaria de ser objeto de aprimoramentos e acréscimos executados pelos papas ao longo dos séculos. Entre eles, citamos a imponente cinta de fortificação elevada como proteção contra as invasões no final do século IX, o campanário e a admirável porta bizantina do século XI, e ainda os mosaicos da fachada, de Pietro Cavallini, o belo claustro dos Vassalletto, o célebre baldaquino gótico de Arnolfo di Cambio e o candelabro pascal de Nicola d’Angelo e Pietro Vassalletto, do século XIII. Essa foi a era de ouro da maior basílica de Roma, superada apenas com a consagração da nova Basílica de São Pedro, em 1626. Meta sagrada de peregrinações da cristandade, a Basílica de São Paulo Fora dos Muros é famosa por suas obras de arte.

Na noite de 15 de julho de 1823, um incêndio destruiu esse testemunho único de épocas paleocristãs, bizantinas, do Renascimento e do Barroco. A basílica foi reconstruída idêntica ao que era antes, com a reutilização dos elementos poupados pelo fogo. Papa Gregório XVI, em 1840, consagraria o altar da Confissão e o transepto.

E os aprimoramentos continuavam. Em 1928, foi acrescentado o pórtico da 150 colunas. Nos dias de hoje, foi a vez do túmulo do Apóstolo vir à luz, ao mesmo tempo em que uma série de importantes reformas se beneficiam, como no passado, da generosidade dos cristãos de todas as partes do mundo.

A longa série de medalhões representa todos os papas da história, e foi iniciada sob o pontificado de Leão Magno, no século V, testemunhando de modo extraordinário o “primado reconhecido pelos fiéis de todos os lugares à grandíssima Igreja constituída em Roma pelos gloriosos apóstolos Pedro e Paulo” (Santo Irineu, século II).

São Paulo Fora dos Muros é um vasto complexo extraterritorial (Motu proprio do papa Bento XVI, 30 de maio de 2005), administrado por um Arcipreste.

Além da Basílica papal, o conjunto compreende uma abadia beneditina muito antiga, restaurada por Odon de Cluny em 936, bastante atuante nos dias de hoje. Os monges beneditinos da antiquíssima abadia, edificada junto ao túmulo do Apóstolo pelo papa Gregório II (715-731), promovem o ministério da Reconciliação (ou Penitência) e a realização de eventos ecumênicos.

É na Basílica que se conclui todos os anos solenemente, no dia da conversão de São Paulo, 25 de janeiro, a Semana pela Unidade dos Cristãos.

O Santo Padre Bento XVI, em 28 de junho de 2007, esteve na Basílica para promulgar o “Ano Paulino”, com a finalidade de celebrar o Bimilenário do nascimento de São Paulo. O Ano Paulino foi realizado a partir de 28 de junho de 2008 a 29 de junho de 2009.