Os apóstolos obedeceram à ordem de Jesus de pregar as boas novas em toda a Terra. No ano 47, os irmãos em Antioquia enviaram Paulo e Barnabé numa viagem de pregação. Nessa viagem, Paulo e Barnabé pregaram em muitos lugares da Ásia Menor, como Derbe, Listra e Icónio.

Paulo e Barnabé falavam das boas novas com todas as pessoas. Pregavam a ricos e pobres, a jovens e idosos. E muitos começaram a acreditar em Jesus. Quando Paulo e Barnabé pregaram a Sérgio Paulo, o governador de Chipre, um feiticeiro tentou impedi-los. Paulo disse ao feiticeiro:

— Jeová está contra ti!

Naquele preciso momento, o feiticeiro ficou cego. Quando o governador viu isso, ficou impressionado e decidiu tornar-se cristão.

Paulo e Barnabé pregavam em todo o lado. Pregavam de casa em casa, nas feiras, nas estradas e nas sinagogas. Quando passaram por Listra, curaram um homem coxo. As pessoas que viram esse milagre acharam que eles eram deuses e começaram a adorá-los. Mas Paulo e Barnabé disseram:

— Não façam isso. Somos apenas homens. Adorem a Deus!

Depois, alguns judeus começaram a dizer mal de Paulo e Barnabé às pessoas de Listra. Por isso, elas apedrejaram Paulo e arrastaram-no para fora da cidade, pensando que tinha morrido. Mas Paulo ainda estava vivo. Sem perder tempo, os irmãos vieram ajudá-lo e levaram-no de volta para a cidade. Algum tempo depois, Paulo voltou para Antioquia.

No ano 49, Paulo começou outra viagem de pregação. Primeiro, ele  visitou novamente os irmãos na Ásia Menor. Depois, viajou para mais longe ainda, até à Europa. Ele foi a Atenas, Éfeso, Filipos, Tessalónica e outras cidades. Lucas, Silas e um jovem chamado Timóteo também viajaram com Paulo. Eles formaram congregações e ajudaram-nas a crescer. Paulo ficou um ano em Corinto para fortalecer os irmãos de lá. Ele pregou, ensinou e escreveu cartas a muitas congregações. Paulo também trabalhou. Ele fazia tendas. Mais tarde, voltou para Antioquia.

No ano 52, Paulo começou uma terceira viagem de pregação, na Ásia Menor. Subiu até chegar a Filipos e, depois, desceu até Corinto. Paulo ficou vários anos em Éfeso a pregar as boas novas, a curar pessoas e a ajudar a congregação. Ele também ia todos os dias a uma escola fazer discursos. Muitos dos que escutavam tornavam-se cristãos. Depois de pregar em muitos sítios, Paulo foi para Jerusalém.