Après sa “conversion”, sur la route de Damas, Paul sillonne une partie de l’Asie mineure (Turquie actuelle), de la Syrie et de l’Arabie (actuelle Jordanie), jusqu’à Jérusalem, avant de passer en Europe, en Grèce, puis à Rome. On peut raisonnablement dater ses voyages dans un intervalle de quelques années autour de l'année 50.

Premier voyage

D’Antioche à Chypre et au sud de l’Anatolie (Pergé, Antioche de Pisidie, Iconium, Lystre, Derbé), Paul et Barnabé prêchent avec fougue la Bonne Nouvelle de la résurrection et du salut en Jésus, dans les synagogues, et fondent des communautés. Les Juifs se divisent alors, et Paul se tourne, aussi, vers les païens.

Deuxième voyage

Le premier objectif de Paul, accompagné de Silas, est de rencontrer les communautés qu’il a créées en Anatolie du sud (à Lystre, il rencontre Timothée qui continue le voyage avec eux). Ils poursuivent vers le nord-ouest, jusqu’aux Dardanelles, à Troie, d’où ils passent en Grèce ; Paul fonde des Églises à Philippes, Thessalonique, Bérée, Athènes et Corinthe. Il retourne ensuite à Antioche, sa base, où l'on entend pour la première fois le nom de « chrétiens », en passant par Éphèse et Césarée.

Troisième voyage

C'est un voyage de consolidation : Paul retourne voir les Églises créées en Anatolie et en Grèce, avec Timothée et Tite. Il réembarque vers Tyr, Césarée, et Jérusalem, où il est arrêté.

Voyage de la captivité

Le voyage du prisonnier à Rome n'est pas un voyage missionnaire, mais son activité d'évangélisateur ne cessera pas.