Potem wrócił do Damaszku i tam spotkał go ten sam los, jaki on wcześniej sam chciał zgotować uczniom Chrystusa: „Żydzi postanowili go zgładzić”. Uratowała go ucieczka zorganizowana przez uczniów. Wtedy nawrócony Szaweł po raz pierwszy udał się do Jerozolimy. On sam tak pisze o tej wizycie w Liście do Galatów: „Trzy lata później udałem się do Jerozolimy dla poznania się z Kefasem, zatrzymując się u niego piętnaście dni. Spośród zaś innych, którzy należą do grona apostołów, widziałem jedynie Jakuba, brata Pańskiego”. Relacja doskonale harmonizuje z opisem z Dziejów Apostolskich, choć Paweł nie wspomina o lęku uczniów Chrystusa, którzy nie wierzyli, że on „jest uczniem”.

Wszystko zmieniło się, gdy Pawłem zaopiekował się Barnaba. Sam Barnaba był nawróconym Żydem. Pochodził z Cypru, wyspy leżącej blisko rodzinnych stron Szawła. Może znali się stamtąd, a może poznali się w Jerozolimie, w szkole Gamaliela. Barnaba był bowiem lewitą i mógł uczyć się w tej znakomitej szkole rabinackiej.

Paweł opuścił Jerozolimę i udał się do rodzinnego Tarsu w Cylicji. Tam znów odnalazł go Barnaba i zaprowadził do Antiochii, centrum Kościoła, gdzie po raz pierwszy uczniów Pana nazwano chrześcijanami. I tu doszło do kolejnego ważnego objawienia się Bożej woli, gdzie widomym się stało, że drogi Kościoła prowadzi Duch Święty: „W Antiochii… gdy odprawiali publiczne nabożeństwo i pościli, rzekł Duch Święty: »Wyznaczcie mi już Barnabę i Szawła do dzieła, do którego ich powołałem«”. I wówczas obaj ewangelizatorzy wyruszyli w pierwszą podróż misyjną. Paweł odbył potem jeszcze kolejne dwie, przemierzając wschodnią część rzymskiego imperium. Nawracał i przekonywał do pójścia za Chrystusem. Odnosił spektakularne sukcesy, ale też co rusz był prześladowany. Wciąż w jego losach sprawdzały się słowa Pana, które powiedział o nim w objawieniu Ananiaszowi w Damaszku: „On zaniesie moje imię do pogan i królów, i do synów Izraela. I pokażę mu, jak wiele będzie musiał wycierpieć dla mego imienia”.