В связи с этим стоит позднейшее сообщение (в похвальном слове ап. Варнаве кипрского монаха Александра — не раньше VI в.), что Варнава был учеником Гамалиила и имел своим соучеником Савла. Спустя некоторое время, когда в Иерусалиме получено было известие о распространении христианства между антиохийскими язычниками, Варнава по поручению апостолов отправился в Антиохию. Цель этого посольства не указана, но Дееписатель сообщает, что Варнава, «прибыв и увидев благодать Божию, возрадовался и убеждал всех держаться Господа искренним сердцем; ибо он был муж добрый и исполненный Духа Святого и веры. И приложилось довольно народу к Господу» (Деян. 11: 21—24 [цит.: 23—24]). Ввиду такого успеха Варнава пошел в Таре, разыскал там Савла и привел его в Антиохию в качестве сотрудника: «Целый год собирались они в церкви и учили немалое число людей; и ученики в Антиохии в первый раз стали называться христианами» (11: 25—26 [цит.: 26]). После путешествия в Иерусалим для передачи милостыни по случаю бывшего там голода (в 44 г. по P. X.) Варнава и Савл, по повелению Духа Святого, антиохийской Церковью были отделены на апостольское служение (И: 30; 12: 25; 13:2-4) и вместе с племянником Варнавы Иоанном Марком отправились в великое благовестническое путешествие (ок. 45 г.). Через Селевкию Савл и Варнава, в сопровождении Марка, прибыли на Кипр, прошли с проповедью весь остров от востока до запада, отсюда отправились в Малую Азию и через Пергию пришли в Антиохию Писидийскую, проповедовали и совершали знамения, затем [отправились] в Иконию и Листру. После продолжительной и плодотворной деятельности из Дервии они возвратились прежним путем, минуя Кипр, в столицу Сирии, «утверждая души учеников, увещевая пребывать в вере и поучая, что многими скорбями надлежит нам войти в Царствие Божие, и рукоположивши им пресвитеров в каждой церкви» (глл. 13—14 [цит.: 14: 22—23]). Иоанн Марк еще в Пергии отделился от них и возвратился в Иерусалим. Во время этого путешествия Варнава в повествовании Дееписателя отступает на задний план, и именно с того момента (13: 9), когда он [(Лука)] начинает именовать Савла Павлом (ср. И: 30; 12: 25; 13: 1, 2, 7 и 13: 43, 46, 50; 14: 20; 15: 2, 22, 35). Во время этого путешествия собственно Павел является проповедником-миссионером (ср. 13:16; 14: 8 слл.; 14: 19 сл.); в Листре «называли Варнаву Зевсом, а Павла Ермирм, потому что он начальствовал в слове» (14:12). Возвратившись в Антиохию, Павел и Варнава собрали Церковь и «рассказали все, что сотворил Бог с ними и как Он отверз дверь веры язычникам. И пребывали там немалое время с учениками» (14: 27-28).
Когда в Антиохии некоторыми пришедшими из Иудеи был возбужден вопрос об обязательности закона Моисеева для христиан, обращенных из язычества, Павел и Варнава выступили на защиту христианской свободы. После «немалого состязания» «положили Павлу и Варнаве и некоторым другим из них отправиться по сему делу к апостолам и пресвитерам в Иерусалим» (15: 2). На Апостольском соборе они защищали против иудействующих свободу христиан из язычников от соблюдения ветхозаветного закона, подтверждая свои доводы повествованием о том, какие знамения и чудеса Бог сотворил через них среди язычников. После собора с посланием от него они возвратились в Антиохию, признанные и старейшими апостолами в своем служении апостолов среди языков (Гал. 2: 1-10). В Антиохии Варнава, подобно пришедшему сюда ап. Петру, основываясь на постановлении собора, имел полное общение с христианами из язычников, принимал участие в их столе, не обращая внимания на иудейски законническое различие чистого и нечистого. Но когда в Антиохию прибыли иудео-христиане, Петр неожиданно стал «таиться и устраняться, опасаясь обрезанных»; «вместе с ним лицемерили и прочие иудеи, так что даже Варнава был увлечен их лицемерием», в чем все и были обличены ап. Павлом (Гал. 2: 11 слл.).
По истечении некоторого времени Павел пригласил Варнаву посетить братьев по всем городам, в которых они вместе проповедовали слово Господне.
Варнава хотел взять с собой Иоанна Марка, «но Павел полагал не брать отставшего от них в Памфилии и не шедшего с ними на дело, на которое они были посланы. Отсюда произошло огорчение, так что они разлучились друг с другом, и Варнава, взяв Марка, отплыл в Кипр, а Павел, избрав себе Силу, отправился, быв поручен братиями благодати Божией» (15: 36—40 [цит.: 38—40]), во второе великое благовестническое путешествие.