Pavel se narodil do židovské rodiny žijící v Tarsu v Malé Asii a vedle latinského jména Paulus měl i židovské jméno Saul, ale již od narození byl římským občanem. Občanství pravděpodobně získal jeho otec či děd jako odměnu za zásluhy pro Tarsos. Skutečnost, že byl římským občanem, mu také nejednou usnadnila situaci, někdy dokonce i zachránila život. Vzdělával se v Jeruzalémě u proslulého židovského učitele Gamaliela, získal tak velmi dobré vzdělání a vládl velmi dobrou řečtinou.
Legenda o obrácení:
Později se přidal ke skupině farizejů a stal se z něho horlivý pronásledovatel křesťanů, byl také přítomný kamenování svatého Štěpána. Když byl na cestě do Damašku, kam jel zatknout všechny tamější křesťany, byl cestou oslepen světlem z nebe a slyšel promluvit hlas: "Saule, proč mě pronásleduješ?“ Když se zeptal, kdo k němu mluví, hlas pravil: „Já jsem Ježíš, kterého ty pronásleduješ. Vstaň, jdi do města a tam se dovíš, co máš dělat.“
