A primeira vez que aparece Paulo, na Bíblia, é em Atos dos Apóstolos, no capítulo 7, quando Estêvão foi apedrejado. No versículo 58 se diz: As testemunhas depuseram seus mantos aos pés de um jovem chamado Saulo. E no primeiro versículo do capítulo seguinte (Atos dos Apóstolos 8) se diz, sobre o martírio de Estêvão: "Saulo estava de acordo com a sus execução".

A mudança na vida de Saulo é contada no capítulo 9 de Atos de Apóstolos.

Invés, a primeira vez que Saulo é chamado com o nome de Paulo acontece em Atos dos Apóstolos 13,9: "Então Saulo, que também se chamava Paulo, repleto do Espírito santo..."

Paulo era o nome romano que o apóstolo usava, enquanto que Saulo derivava do hebraico (Saul). Era normal que as pessoas tivessem, naquela época, dois nomes. João, por exemplo, também se chamava Marcos (Atos dos apóstolos 12,12).