Apoštolové poslouchali Ježíšův příkaz, aby mluvili o dobré zprávě po celé zemi. V roce 47 n. l. bratři v Antiochii poslali Pavla a Barnabáše na kazatelskou cestu. Ti dva obětaví muži procestovali celou Malou Asii a dostali se například do Derbé, Lystry a Ikonia.

Mluvili s bohatými i chudými, mladými i starými. Hodně lidí začalo věřit v Ježíše. Když si o něm Pavel a Barnabáš povídali s vládcem Kypru Sergiem Paulem, jeden kouzelník se jim v tom snažil zabránit. Pavel mu řekl: „Jehova tě potrestá!“ Kouzelník okamžitě oslepl. Když to Sergius Paulus viděl, stal se křesťanem.

Pavel a Barnabáš mluvili o Ježíšovi všude – dům od domu, na tržištích, na cestách a v synagogách. Když v Lystře uzdravili muže, který nemohl chodit, lidi si mysleli, že jsou bohové, a chtěli je uctívat. Pavel a Barnabáš jim ale řekli: „Uctívejte jenom Boha! My jsme obyčejní lidé.“ Pak do Lystry přišli nějací Židé a navedli místní obyvatele, aby na Pavla zaútočili. Ti začali Pavla kamenovat, a když si mysleli, že je mrtvý, odtáhli ho za město. Pavel byl ale pořád naživu. Bratři mu okamžitě přišli na pomoc a vzali ho zpátky do města. O něco později se Pavel vrátil do Antiochie.

Roku 49 n. l. se Pavel vydal na další cestu. Nejdřív se vrátil za bratry v Malé Asii, aby zjistil, jak se jim daří. A pak šel  oznamovat dobrou zprávu ještě dál, do Evropy. Navštívil Atény, Efez, Filipy, Tesaloniku a další města. Na cestách ho doprovázeli Silas, Lukáš a mladý Timoteus. Spolu s Pavlem zakládali sbory a pomáhali jim, aby byly silné. Rok a půl Pavel zůstal v Korintu a povzbuzoval tam bratry. Mluvil s lidmi o dobré zprávě, vyučoval a psal dopisy sborům. Taky pracoval jako výrobce stanů. Časem se vrátil do Antiochie.

Později, v roce 52 n. l., Pavel vyrazil na svoji třetí cestu a začal v Malé Asii. Cestoval na sever až do Filip a pak dolů do Korintu. Několik let strávil v Efezu, kde vyučoval, uzdravoval a pomáhal místnímu sboru. Taky měl každý den přednášky v sále jedné školy. Hodně lidí poslouchalo, co Pavel učí, a změnilo se. Potom co oznamoval dobrou zprávu v mnoha zemích, se nakonec vydal na cestu do Jeruzaléma.