«Apostolo» è il titolo principale che Paolo si attribuisce nelle sue lettere (vedi ad esempio Rm 1,1; 1Cor 1,1; Ef 1,1; Col 1,1) e che la tradizione cristiana successiva gli ha poi confermato; non gli è invece attribuito negli Atti. Il titolo è la traslitterazione del termine greco ἀπόστολος, apòstolos, che significa «inviato». In senso proprio, il titolo è applicato nei testi del Nuovo Testamento ai dodici apostoli che seguirono Gesù durante il suo ministero pubblico. Paolo, che non compare nei vangeli e che non fece parte del suo seguito, non può essere identificato come apostolo in tal senso – lui stesso specifica infatti in Rm 1,1 di essere «apostolo per vocazione». Come Paolo, del resto, anche altri personaggi del Nuovo Testamento sono detti «apostoli», sebbene non lo siano stati in senso proprio (Barnaba in At 14,14; Andronico e Giunia in Rm 16,7; Sila e Timoteo vescovo in 1Ts 1,1; 2,6; Apollo in 1Cor 4,9). In alcuni passi (Rm 11,13; Gal 2,8), Paolo si definisce «apostolo dei Gentili».