A Bíblia não conta o martírio dos apóstolos, exceto a menção a Tiago, morto pela mão de Herodes (Atos 12,2), além do martírio de Estêvão, um dos 7 escolhidos para ajudar os apóstolos (Atos 6).
Atos dos Apóstolos, que conta a história da evangelização de Paulo, termina mencionando que Paulo se encontrava na prisão, mas diz que podia receber as pessoas que vinham até ele (Atos 28,30-31).
Na carta que Paulo escreveu a Timoteo ele, invés, prevê a sua morte: "Quanto a mim, o meu sangue está para ser oferecido em libação e chegou o tempo da minha partida" (2Timóteo 4,6).
A primeira notícia histórica sobre a morte do apóstolo das gentes se encontra em um texto fora da Bíblia. Está escrito na Carta de Clemente aos Coríntios. O bispo de Roma escreve por volta do ano 95, a cerca de 30 anos depois da morte de Paulo. Clemente convida os cristãos da cidade grega a espelharem-se no exemplo dos apóstolos. E logo depois de mencionar o martírio de Pedro, ele diz:
"Por causa do ciúme e da discórdia Paulo foi obrigado a mostrar-nos como se consegue o prêmio da paciência. Preso 7 vezes, exiliado, apedrejado, foi aralto de Cristo no Oriente e no Ocidente e, por sua fé, conquistou uma glória pura. Depois de ter anunciado a justiça a todo mundo e, depois de ter chegado à extremidade do Ocidente, sofreu o martírio diante dos governantes; assim partiu deste mundo e chegou ao lugar santo, tornando-se com isso o maior modelo de paciência" (1Clemente 5,2).
O martírio em si é contado pelo livro chamado Atos de Paulo, que foi escrito por volta do ano 200, a cerca de 150 anos depois da morte do apóstolo. Conta-se que Nero o condenou à morte por decapitação, que foi logo executada (9,5). A sua morte provavelmente aconteceu em concomitência com a perseguição de Nero, depois do incêndio de Roma, em julho do ano 64.
Tertuliano, por volta do ano 200, diz que Paulo obteve a cora do martírio, em Roma, da mesma maneira que João Batista, isto é, sendo decapitado (De Praecription Haeret. 36,3).
Em relação ao local, diz-se que aconteceu nas "Acquae Salviae", na Via Laurentina, com um triplo pulo da sua cabeça, cada pulo provocando o nascer de uma fonte de água. Por isso o local foi chamado "Três Fontes". Ainda hoje, no local existe uma importante basílica.
O seu corpo foi colocado na via Ostiense, onde o Imperador Constantino construiu uma igreja e até hoje existe ali a Basílica São Paulo Fora dos Muros.
