Dado que este período carece da documentação dos Atos, está envolvido na mais completa obscuridade; nossas únicas fontes são algumas tradições disperssas e as citas disperssas das epístolas. Paulo quis passar pela Espanha desde muito tempo antes (Rom., xv, 24, 28) e não há provas de que mudaria seu plano. Já no fim do seu cativeiro, quando anuncia sua chegada a Filemon (22) e aos Filipenses (ii, 23-24), não parece considerar esta visita como iminente, dado que compromete aos filipenses enviar-lhes um mensageiro cuando esteja concluído o seu julgamento e, portanto, ele preparava outra viagem antes do seu retorno ao oriente. Sem necessidade de citar os testemunhos de São Cirilo de Jerusalém, são Epifanio, São Jerônimo, São Crisóstomo e teodoreto diremos finalemtne que el testemunho de São Clemente de Roma, bem conhecido, o testemunho do "Canon Muratorio", e a "Acta Pauli" fazem mais que provável a viagem de Paulo à Espanha. Em todo caso não pôde permanecer muito tempo por lá, devido à sua pressa por visitar outras Igrejas do leste. Pôde entretanto voltar à Espanha através da Gália, como pensaram alguns padres, e não à Galácia, aonde Crescêncio foi enviado mais tarde. (II Tim., iv, 10). É verossímil que, depois, chegaria a cumprir sua promessa de visitar seu amigo Filemon e que, en tal ocasião, visitaria as Igrejas do vale de Licaônia, Laodicéia, Colossos, e Hierápolis.

A partir deste momento o itinerário se torna sumamente incerto por mais que os seguintes acontecimentos parecem estar indicados nas epístolas pastorais: Paulo permaneceu em Creto o tempo necessa'rio para fundar novas Igrejas, cujo cuidado e organização deixou nas mãos do seu colega Tito (Tit., i, 5). Foi depois a Éfeso e rogou a Timóteo, que já estava lá, que permaneceria aí até seu regresso enquanto Paulo se dirigia à Macedônia (I Tim., i, 3). Nesta ocasião visitou, como havia prometido, aos filipensses (Fil., ii, 24), e , naturalmente, também passou a ver os tessalonicensesalonicensses. A carta a Tito e a primeira epístola a Timóteo devem datar deste período; parece que foram escritas ao mesmo tempo aproximadamente, pouco depois de ter deixado a Éfeso. A questão é saber se foram enviadas desde Macedônia ou desde Corinto, como parece ser mais provável. O Apóstolo instrui a Tito para que se reuna com ele em Nicópolis de Epiro donde pensa passar o verão (Titus, iii, 12). Na primavera seguinte deve ter cumprido seu plano de volta a Ásia (I Tim, iii, 14-15). Aqui ocorreu o obscuro episódio da sua prisão, que provávelmente ocorreu em Trôade; isso explicaría o fato de ter deixado uns livros e roupas que necessitou depois (II Tim., ib, 13). De lá foi a Éfeso, capital da proovincia de Ásia, onde o abandonaram todos aqueles que ele pensava que lhe haviam sido fiéis (II Tim., i, 15). Enviado a Roma para ser julgado, deixou a Trófimo doente em Mileto e a Erasto, outr dos seus companheiros, que permaneceram em Corinto por razões nunca esclarecidas (II Tim., iv, 20). Quando Paulo escreveu sua segunda epístola a Timóteo desde Roma, acreditava que toda esperanza humana estava perdida (iv, 6).; nela pede a seu discípulo que venha ver-lhe o mais rápido possível, porque estava apenas com Lucas. Não sabemos se Timóteo foi capaz de ir a Roma antes da morte do Apóstolo.

Uma antiga tradição torna possível estabelecer os seguintes pontos: (1) Paulo sofreu o martírio cerca a Roma na praça chamada Aquae Salviae (hoje Piazza Tre Fontane), um pouco ao oeste da Via Ostia, cerca de três quilômetros da explêndida basílica de São Paulo Extra Muros, lugar onde foi enterrado. (2) O martírio ocorreu no fim do reinado de Nero, no décimo segundo ano (São Epifanio), no décimo terceiro (Eutalio), ou no décimo quarto (São Jerônimo). (3) De acordo com a opinião mais comum, Paulo sofreu o martírio no mesmo dia do mesmo ano que Pedro; alguns padres latinos disputam se foi o mesmo dia mas não do mesmo ano; a testemunha más antiga, São Dionisio o Corinto, disse somente Kata ton auton Kairon, o que pode ser traduzido por "ao mesmo tempo" ou "aproximadamente ao mesmo tempo". (4) Durante tempo imemorável, a solenidade dos apóstolos Pedro e Paulo se celebra no dia 29 de Junho, que é o aniversário, seja da morte, seja do traslado de suas relíquias. O Papa ía antigamente com seus acompanhantes a São Paulo Extra Muros depois de celebrar em São Pedro, ainda que a distância entre as duas basílicas (aprox. oito quilômetros) fazia a cerimônia cansativa, particularmente nesta época do ano. Assim surgiu o costume de transferir ao dia seguinte (30 de junho) a comemoração de São Paulo. A festa da conversão de São Paulo (25 de janeiro) tem origem comparativamente recente. Há razões para crer que este dia foi celebrado para marcar o traslado das relíquias de São Paulo a Roma, posto que assim aparece no Martirologio Hieronimiano. Esta festa é desconhecida na igreja grega (Dowden, "The Church Year and Kalendar", Cambridge, 1910, 69; cf. Duchesne, "Origines du culte chrétien", Paris 198, 265-72; McClure, "Christian Workship", London, 1903, 277-81).