Cette recommandation supérieure, cette voix qui venait des arcanes célestes, a résonné dans le cœur de l'ex-rabbin comme un cantique de victoire spirituelle. Il sentait qu'il venait de traverser un immense désert pour trouver à nouveau le doux message éternel du Christ. Pour conquérir la dignité spirituelle, il n'avait ressenti que des souffrances depuis sa pénible cécité de Damas. Il avait ardemment désiré Jésus. Il vécut une soif brûlante et terrible. Il avait demandé en vain la compréhension à ses amis, en vain il avait cherché la tendre douceur d'une famille. Mais, maintenant, que la parole du Plus-Haut l'appelait au service, il était plein de joies infinies. C'était le signe qu'il avait été considéré digne des efforts confiés aux disciples. Il se dit combien ses douleurs passées lui semblaient petites et infantiles, comparées à la joie immense qui inondait son âme, alors Saûl de Tarse a pleuré copieusement éprouvant de merveilleuses sensations. Aucun de ses frères qui étaient présents, pas même Barnabe, ne pouvait mesurer la grandeur des sentiments que ces larmes révélaient. Pris d'une profonde émotion, l'ex-docteur de la Loi reconnaissait que Jésus daignait accepter ses oblations de bonne volonté, ses luttes et ses sacrifices. Le Maître l'appelait et pour répondre à son appel, il irait aux confins du monde.
De nombreux compagnons collaborèrent aux premières mesures pour la bonne marche de cette entreprise.
Peu de temps après, pleins de confiance en Dieu, Saûl et Barnabe, suivis de Jean- Marc, saluaient leurs frères, en route vers Séleucie. Le voyage vers le littoral se fit dans un climat d'une très grande joie. De temps en temps, ils se reposaient aux bords de l'Oronte pour une collation salutaire. À l'ombre des chênes, dans la paix des forêts parsemées de fleurs, les missionnaires commentaient leurs premiers espoirs.
À Séleucie, l'attente pour prendre un bateau ne fut pas très longue. La ville était toujours pleine de pèlerins qui partaient pour l'Occident et était fréquentée par un grand nombre de navires de tous genres. Enthousiasmé par l'accueil que leurs frères de foi leur avaient réserve, Barnabe et Saûl embarquèrent pour Chypre sous l'impression d'émouvants et doux adieux.
Ils arrivèrent sur l'île avec le jeune Jean-Marc, saris grand incident. Ils s'arrêtèrent à Citiuni pendant plusieurs jours, là Barnabe résolut plusieurs problèmes d'ordre familial.
Avant de partir, un samedi, ils visitèrent la synagogue dans l'intention d'initier leur mouvement. Comme chef de mission, Barnabe prit la parole et chercha à conjuguer le texte de la Loi étudié ce jour avec les leçons de l'Évangile pour souligner la supériorité de la mission du Christ. Saûl remarqua que son compagnon exposait le sujet avec un respect légèrement excessif vis-à-vis des traditions judaïques. Il était évident qu'il désirait, avant tout, conquérir la sympathie de l'auditoire ; et en certains points, il semblait craindre d'initier le travail, d'entamer la lutte si contraire à son tempérament. Les Israélites furent surpris, mais satisfaits. Observant ce tableau, Saûl ne s'est pas senti entièrement convaincu. Faire des reproches à Barnabe serait une marque d'ingratitude et d'indiscipline ; être en accord avec le sourire des compatriotes qui persévéraient dans les erreurs de l'imposture pharisienne serait nier leur fidélité à l'Évangile.
Il chercha à se résigner et attendit.
La mission avait couvert de nombreuses localités où des vibrations de sympathie s'étaient largement manifestées. À Amathonte, les messagers de la Bonne Nouvelle s'arrêtèrent plus d'une semaine. La parole de Barnabe était profondément complaisante. Il cherchait avant tout à ne pas offenser les susceptibilités judaïques.