Arrivés à Salamine, ils annoncèrent la parole de Dieu dans les synagogues des Juifs. Ils avaient aussi Jean pour aide.
Ensuite, ils traversèrent toute l'île jusqu'à Paphos, où ils trouvèrent un magicien, un prétendu prophète juif appelé Bar-Jésus. Il faisait partie de l'entourage du gouverneur Sergius Paulus, un homme intelligent. Ce dernier fit appeler Barnabas et Saul et exprima le désir d'entendre la parole de Dieu. Mais Elymas le magicien - c'est en effet ce que signifie son nom - s'opposait à eux et cherchait à détourner le gouverneur de la foi. Alors Saul, appelé aussi Paul, rempli du Saint-Esprit, fixa les regards sur lui et dit: «Homme plein de toute sorte de ruse et de méchanceté, fils du diable, ennemi de toute justice, ne vas-tu pas cesser de pervertir les voies droites du Seigneur? Maintenant, voici que la main du Seigneur est sur toi: tu seras aveugle et pour un temps tu ne verras pas le soleil.» L'obscurité et les ténèbres tombèrent immédiatement sur lui et il se tournait de tous côtés en cherchant quelqu'un pour le guider. Quand il vit ce qui était arrivé, le gouverneur crut, frappé qu'il était par l'enseignement du Seigneur.
Paul et ses compagnons embarquèrent à Paphos pour se rendre à Perge en Pamphylie, mais Jean se sépara d'eux et retourna à Jérusalem.