Toutefois après avoir coopéré pendant quelque temps à la consolidation de l'église et considérant qu'Aquiles et Prisca se trouvaient bien installés et satisfaits, l'apôtre décida de partir vers de nouveaux horizons. En vain ses frères voulurent l'en dissuader, le suppliant de rester en ville un peu plus longtemps. Il promit de revenir dès que les circonstances le lui permettraient et prétexta devoir aller à Jérusalem, porter à Simon Pierre le fruit des collectes rassemblées pendant des années consécutives sur les lieux qu'il avait parcourus. Le fils de Zébédée, qui connaissait son ancien projet, lui donna raison d'entreprendre ce voyage sans plus tarder.
Comme ils se trouvaient à nouveau à ses côtés, Silas et Timothée lui tinrent compagnie lors de cette nouvelle excursion.
Passant par d'énormes difficultés, mais prêchant toujours la Bonne Nouvelle avec un véritable enthousiasme dévotionnel, ils arrivèrent au port de Césarée où ils restèrent quelques jours pour instruire les intéressés à la connaissance de l'Évangile. De là, ils se sont dirigés à pied vers Jérusalem, distribuant des consolations et des guérisons tout le long du chemin. Arrivés à la capitale du judaïsme, l'ex-pêcheur de Capharnaum les reçut avec une immense joie. Simon Pierre présentait une grande fatigue physique vu les luttes terribles et incessantes affrontées pour que l'église supporte les tempêtes acharnées sans trop d'émoi. Ses yeux, malgré tout, gardaient la même sérénité caractéristique aux fidèles disciples.
Paul lui remit joyeusement la petite fortune dont l'application allait assurer une plus grande indépendance à l'institution de Jérusalem pour le juste développement de l'oeuvre du Christ. Ému, Pierre le remercia et l'embrassa les larmes aux yeux. Les pauvres, les orphelins, les vieux abandonnés et les convalescents auraient désormais une école bénie de travail sanctifiant.
Pierre remarqua aussi que l'ex-rabbin semblait las. Très maigre et particulièrement pâle, les cheveux déjà grisonnants, tout en lui dénonçait l'intensité des luttes endurées. Ses mains et son visage étaient pleins de cicatrices.
Face à cela, l'ex-pêcheur lui a parlé avec enthousiasme de ses épîtres qui se répandaient dans toutes les églises et qui étaient lues avec assiduité. Sa grande expérience des problèmes d'ordre spirituel lui donnait la conviction que ces lettres avaient été écrites sous l'inspiration directe du Maître divin. Paul de Tarse reçut ce commentaire avec émotion vu la spontanéité manifestée par son compagnon. De plus - ajouta Simon avec plaisir -, il ne pouvait être d'élément éducatif d'une portée plus élevée que celui-ci. Il connaissait des chrétiens de Palestine qui gardaient de nombreuses copies du message aux Thessaloniciens. Les églises de Joppé et d'Antipatris, par exemple, commentaient les épîtres phrase après phrase.
L'ex-rabbin ressentit un immense réconfort pour continuer sa lutte rédemptrice.
Après quelques jours, il partit pour Antioche avec quelques disciples. Il se reposa un peu auprès de précieux compagnons, mais sa puissante capacité de travail ne lui permettait pas de plus longs arrêts.
À cette époque, il ne passait pas une semaine sans recevoir un émissaire venant de diverses églises qui se trouvaient dans les endroits les plus retirés. Antioche de Pisidie récapitulait ses difficultés ; Iconie demandait de nouvelles visites ; Bérée suppliait des mesures ; Corinthe manquait d'éclaircissements ; Colosse insistait pour recevoir sa présence au plus vite. Profitant des compagnons présents à cette occasion, Paul de Tarse leur envoyait de nouvelles lettres, répondant à tous avec la plus grande affection. Dans de telles circonstances, l'apôtre des gentils ne fut jamais plus seul dans sa tâche évangélisatrice. Toujours assisté par de nombreux disciples, ses épîtres, qui resteraient pour les générations de chrétiens à venir, sont pour la plupart pleines de références personnelles douces et aimantes.
Une fois son séjour à Antioche terminé, il est retourné à sa ville natale pour y parler des vérités éternelles et réussit à éveiller un grand nombre de tarsiens aux réalités de l'Évangile. Ensuite, il s'est à nouveau enfoncé dans les hauteurs du Taurus pour visiter les communautés de toute la Galatie et de la Phrygie, soulevant l'enthousiasme des compagnons de foi, ce à quoi il passait le plus clair de son temps. Dans cet élan infatigable et incessant, il réussit à recruter de nouveaux disciples de Jésus, distribuant de grands bienfaits dans tous les coins illuminés par sa parole édifiante qui s'accompagnait de faits marquants.
De toute part, les luttes sans trêves, les joies et les douleurs, les angoisses et les amertumes du monde n'arrivaient pas à étouffer ses espoirs en la promesse de Jésus. D'un côté, se trouvaient les rigides Israélites, ennemis entêtés et déclarés du Sauveur ; de l'autre, les chrétiens indécis qui oscillaient entre les besoins personnels et les fausses interprétations. Mais le missionnaire tarsien savait que le disciple sincère doit ressentir les sensations de la « porte étroite » à chaque jour qui passe et ne jamais se laisser guider par le découragement. À tout instant, il renouvelait son intention de tout supporter, d'agir, de faire et de construire pour l'Évangile, entièrement consacré à Jésus-Christ.
Une fois qu'il eut triomphé des luttes, il décida de retourner à Éphèse, désireux de se consacrer au service de l'Évangile d'après les souvenirs de Marie.
Mais il n'y trouva pas Aquiles et Prisca retournés à Corinthe en compagnie d'un certain Apollos qui s'était fait remarquer par sa culture parmi les derniers convertis. Bien qu'il ne prétendit avoir que quelques conversations plus prolongées avec la fille inoubliable de Nazareth, il fut obligé d'affronter une lutte particulièrement sérieuse avec les coopérateurs de Jean. La synagogue avait à cette époque un grand ascendant politique sur l'église de la ville qui menaçait de s'effondrer. L'ex-rabbin perçut le danger et releva le défi sans réserves. Pendant trois mois, il alla discuter à la synagogue à toutes les réunions qui se présentaient. La population, qui était passée par de terribles doutes, semblait peu à peu atteindre une compréhension plus élevée et plus riche de lumières. Un beau jour, alors qu'il multipliait les guérisons merveilleuses, une fois qu'il eut imposé ses mains sur quelques malades, Paul fut encerclé par une clarté Indéfinissable du monde spirituel. Les voix sanctifiées, qui s'étaient manifestées à Jérusalem et à Antioche, ont alors parlé sur la place publique. Ce fait eut une énorme répercussion et donna une plus grande autorité aux arguments de l'apôtre, contredisant ainsi les juifs.
À Éphèse, on ne parlait pas d'autre chose. D'un jour à l'autre, l'ex-rabbin était à l'apogée de la considération. Les Israélites perdaient du terrain sur toute la ligne. Le tisserand profita de l'occasion pour enfoncer des racines évangéliques plus profondes dans les cœurs. En secondant l'effort de Jean, il mit en place dans l'église des services d'assistance aux plus démunis. L'institution s'enrichissait de valeurs spirituelles. Comprenant l'importance de l'organisation d'Éphèse sur toute l'Asie, Paul de Tarse décida d'y prolonger son séjour. Des disciples de Macédoine vinrent se joindre à lui. Aquiles et sa femme revinrent de Corinthe ; Timothée, Silas et Tite quant à eux coopéraient activement en visitant les églises chrétiennes déjà fondées. Ainsi vigoureusement assisté, le généreux apôtre multipliait les guérisons et les bienfaits au nom du Seigneur. En œuvrant pour la victoire des principes du Maître, il avait fait en sorte que beaucoup abandonnent des croyances et des superstitions dangereuses pour se livrer aux bras aimants du Christ.