Wie lange Paulus und Barnabas in Jerusalem blieben, als Paulus zum zweitenmal dort war, ist nicht bekannt. Sie wurden jedoch wahrscheinlich nicht nur von den Führern der Kirche, sondern auch von denen, denen sie durch ihre Gaben in Notzeiten geholfen hatten, freundlich aufgenommen (s. Apg. 11:29, 30). Selbst die Juden mußten die gemeinnützige Hilfsaktion dieser Männer anerkennen.
Wenn Paulus nicht schon beim ersten Besuch nach seiner Bekehrung die Offenbarung empfangen hatte, die in der Apostelgeschichte 22:17–21 erwähnt wird, so geschah dies vielleicht bei seinem zweiten Besuch. Als er „wieder nach Jerusalem kam“, so berichtet er diesmal einer jüdischen Volksmenge, hatte er, während er im Tempel betete, eine Vision von Christus Jesus, der ihn aufforderte, sofort die Stadt zu verlassen, da sein Zeugnis dort nicht aufgenommen würde. Paulus wagte es, der Vision gegenüber Einwände zu erheben; er wies darauf hin, die Juden wüßten sehr wohl, daß er früher die Christen verfolgt, sie gefangengenommen und geschlagen und sich mit der Steinigung des Stephanus einverstanden erklärt hatte. Sicherlich würden sie, so meinte er, davon beeindruckt sein, daß sich seine Überzeugung grundlegend geändert hatte. Doch die einzige Antwort war eine noch deutlichere Aufforderung, die er nicht unbeachtet lassen konnte: „Gehe hin; denn ich will dich ferne unter die Heiden senden!“
Diese Vision, wann er sie auch hatte, zeigt in dramatischer Weise, wie Paulus seine Mission unter den Heiden erkannte. Diese Erkenntnis mag sehr wohl während seines zweiten Besuchs in Jerusalem klarer geworden sein. Bis zu diesem Zeitpunkt hatte er sich, durch seine Rückkehr nach Tarsus und auch in Antiochien, allmählich auf seine besondere Tätigkeit vorbereitet; er wurde mit den Problemen und Bedürfnissen der Heiden immer mehr vertraut, ohne ihre weiter entlegenen Provinzen und Städte aufzusuchen. Nun, wo er zur Zufriedenheit der anderen Apostel bewiesen hatte, daß das Christentum des einzelnen nicht danach bemessen werden konnte, ob er die jüdische Sitte der Beschneidung annahm oder ablehnte, war der richtige Zeitpunkt für eine umfassendere, allgemeinere Mission unter den Heiden gekommen.
Als Paulus und Barnabas von Jerusalem nach Antiochien aufbrachen, nahmen sie einen jungen Verwandten des Barnabas mit, dessen jüdischer Name Johannes war, der uns aber unter dem Namen Markus besser bekannt ist (s. Apg. 12:25; Kol. 4:10). Markus war der Sohn Marias, eines wohlhabenden Mitglieds der Jerusalemer Kirche, in deren Haus Petrus gewohnt haben mag (s. Apg. 12:12–16). Petrus und Markus müssen einander sehr nahegestanden haben; einer stark vertretenen Überlieferung der frühen Kirche gemäß, die Papias im zweiten Jahrhundert niedergeschrieben hat, war Markus der „Interpret“ seines Lehrers Simon Petrus, und Petrus versorgte ihn mit dem Material, das wir heute als das Markusevangelium kennen. Hier sollte ein vielversprechender junger Christ die beiden Missionare begleiten — als ihr Diener oder Gefährte, während er sich auf das geistliche Amt vorbereitete.
Nachdem Paulus nach Antiochien zurückgekehrt war, ereignete sich etwas Bedeutsames. Zur dortigen Kirche gehörte eine Gruppe hervorragender Lehrer und Propheten, und zu ihnen zählten neben Barnabas und Paulus auch Luzius von Kyrene, Manahen und Simon, dessen heidnischer Nachname Niger war. Wie es in der Apostelgeschichte heißt, „sprach der heilige Geist“ zu diesen Obersten der Kirche in jenem Gebiet: „Sondert mir aus Barnabas und Saulus zu dem Werk, dazu ich sie berufen habe.“ Sie gehorchten dem Befehl. Nach einer Zeit des Fastens und Betens wurden Barnabas und Paulus von den übrigen drei Lehrern offiziell mit ihrem Amt beauftragt und auf den Weg geschickt (s. 13:1–3).
Die Missionstätigkeit unter den Heiden hatte nun ernstlich begonnen. Im 13. Kapitel der Apostelgeschichte finden wir den Anfang dessen, was allgemein als die erste Missionsreise des Paulus bekannt ist, sein erstes bemerkenswertes Vordringen in die heidnische Welt. Ungefähr um das Jahr 47 n. Chr. wurden er und Barnabas „ausgesandt ... vom heiligen Geist“ (V. 4), und sie machten sich auf den Weg nach Seleucia, der Hafenstadt Antiochiens, die 25 bis 30 Kilometer entfernt lag. Von dort fuhren sie auf die Insel Zypern, die etwa 110 Kilometer weiter westlich liegt.
Es gab verschiedene Gründe, warum sie mit ihrer Tätigkeit auf Zypern beginnen sollten. Barnabas war dort zu Hause, und das konnte die Einführung erleichtern. Außerdem war der jüdischen Bevölkerung, wie aus der Apostelgeschichte 11:19 hervorgeht, das Christentum nicht unbekannt, denn einige der Jünger, die nach dem Märtyrertod des Stephanus vor der Verfolgung geflohen waren, hatten die Insel besucht. Zypern hatte also zwei Vorteile. Was die Heiden betraf, war es ein noch unberührtes Gebiet, und von den Freunden des Barnabas und den jüdischen Bekehrten, die dort ansässig waren, konnte erwartet werden, daß sie die Missionstätigkeit unterstützen und fördern würden. Ferner machte die geographische Lage Zyperns die Insel zu einem logischen Ausganspunkt für Missionsreisen, die weiter nach Norden und Westen führen sollten. Zypern ist eine Insel von beträchtlicher Größe; an ihrer längsten Stelle mißt sie etwa 260 Kilometer, und in der Mitte befindet sich eine breite fruchtbare Ebene; neben den einheimischen Zyprioten wohnte dort seinerzeit ein großer jüdischer Bevölkerungsteil.
Die beiden Apostel und ihr junger Begleiter Johannes Markus landeten im Hafen von Salamis, das nicht mit der gleichnamigen Insel im Ägäischen Meer verwechselt werden darf. Die Stadt war groß genug für mehrere jüdische Synagogen, und in diesen Synagogen predigten die Apostel, ehe sie die ganze Insel durchzogen. Es wird uns über keine Einzelheiten ihrer Tätigkeit berichtet, bis sie Paphos erreichten, eine Stadt ganz im Südwesten.
In Paphos erlebten sie ihren ersten uns überlieferten Triumph. Sie erweckten dort das Interesse des Sergius Paulus, des römischen „Landvogts“ oder Prokonsuls, der über die Insel herrschte; er forderte sie auf, ihm ihre Botschaft vorzutragen. Dies erweckte die Eifersucht eines gewissen jüdischen Zauberers oder Astrologen, Bar Jesus (Sohn Jesu oder Josuas), der auch unter dem Namen Elymas bekannt war. Anscheinend hatte er eine feste Anstellung im Haushalt des Prokonsuls und war besorgt, daß diese neuen Lehrer seinem Einfluß entgegenwirken würden. Daher „widerstand ihnen Elymas ... und trachtete, daß er den Landvogt vom Glauben abwendete“. Paulus jedoch redete Elymas als ein „Kind des Teufels“ an und kündigte ihm an, daß er eine Zeitlang mit Blindheit geschlagen würde — was auch augenblicklich geschah. Wie wir lesen, „glaubte“ der Prokonsul und „verwunderte sich der Lehre des Herrn“ (s. 13:5–12).
Sergius Paulus war offenbar der erste beim Namen genannte heidnische Konvertit des Paulus. Und es ist nicht ohne Bedeutung, daß von dem Zeitpunkt an der Apostel in der Apostelgeschichte nicht mehr unter seinem jüdischen Namen Saulus, sondern unter seinem römischen Namen Paulus bekannt ist, der den Heiden, denen er hauptsächlich predigen sollte, vertraut klingen würde. Das erste Anzeichen dafür, daß sich der Nachdruck verlagert hat, erhalten wir in der Apostelgeschichte 13:9, der einzigen Stelle, wo die beiden Namen nebeneinander erscheinen: „Saulus ... der auch Paulus heißt“.
Dieses kurze Ereignis, wo der jüdische Zauberer in Verlegenheit geriet und der römische Beamte sich bekehrte, ist auch von einem anderen Gesichtspunkt aus gesehen interessant; Paulus gewann dadurch offenbar an Ansehen. Kurz zuvor werden Barnabas und Saulus (in dieser Reihenfolge) erwähnt, und beinahe unmittelbar danach lesen wir von „Paulus und die um ihn waren“ (V. 13) — Barnabas wird nicht einmal erwähnt; und wenn in den späteren Kapiteln auf die beiden zusammen Bezug genommen wird, geschieht dies beinahe unweigerlich in der Reihenfolge: Paulus und Barnabas, nicht Barnabas und Paulus.
