Святой Варнава ревностно проповедовал слово Божие. По словам книги Деяний апостольских, это был муж добрый и исполненный Духа Святаго и веры (Деян. 11, 24). Совершая апостольские труды, он скорбел о друге своем Савле, который оставался еще упорным врагом Христа и гнал верующих. Но вскоре произошло чудесное обращение Савла ко Христу, чему Варнава был очень обрадован. Спустя три года после своего обращения апостол Павел прибыл в Иерусалим. Но ученики Господни боялись и сторонились его, не веря, что он стал христианином. Тогда святой Варнава представил его апостолам, рассказав им о его чудесном призвании и обращении. Спустя некоторое время святые апостолы отправили Варнаву к новообращенным христианам в Антиохию Сирскую для утверждения их в вере, и он там некоторое время успешно подвизался один, а потом для большего распространения веры Христовой призвал к себе апостола Павла. Целый год они трудились вместе в благовествовании Святого Евангелия, и с каждым днем умножалось число верующих в Антиохии. По случаю наступившего в Иерусалиме голода антиохийские христиане собрали помощь иерусалимским христианам и послали святых апостолов Варнаву и Павла отвести ее голодающим. Исполнив возложенное на них поручение, Павел и Варнава вместе с апостолом Иоанном Марком, племянником Варнавы, вернулись в Антиохию, где пребывали в посте, молитвах и проповедании слова Божия. Когда они вскоре, по повелению Духа Святого, отправились проповедовать имя Христово в других странах, Марк оставил их. Варнава же вместе с Павлом прошли, благовествуя, остров Кипр, были с проповедью слова Божия в Саламине, возвещали учение Христово на острове Пафе, затем прошли Писидию и Иконию и возвратились в Антиохию. Всюду, где бы ни были апостолы, они сначала предлагали свое учение иудеям, жившим там, а потом и язычникам. Успех проповеди был необыкновенный, так что они во многих городах основали церкви. Во время своего апостольского путешествия Варнава и Павел терпели страшные лишения, жестокие гонения и не раз подвергались опасности быть убитыми.
Варнава трудился в распространении и утверждении веры Христовой в Антиохи, откуда в 51 году отправился вместе с Павлом в Иерусалим на Собор апостольский, где обсуждался вопрос, следует ли новообращенных из язычников принуждать к соблюдению закона Моисеева. Здесь Павел и Варнава рассказали об удивительных успехах своей проповеди среди язычников и были утверждены старейшими апостолами в своем служении. Варнаве вместе с Павлом поручили передать христианам Сирии и Киликии соборное послание, которое освобождало новообращенных от соблюдения закона Моисеева. Вскоре после этого апостолы Павел и Варнава решили посетить верующих во всех городах, где они проповедовали слово Божие, и узнать, как те живут. Но между апостолами произошли разногласия: Варнава хотел взять с собой Иоанна Марка, а Павел, памятуя, что Марк уже однажды оставил их, не желал брать его с собой. Поэтому они разошлись: апостол Павел, взяв с собой Силу, пошел в города Сирии, а святой Варнава с Марком отправились на остров Кипр, где пробыли довольно долго, распространяя веру Христову. По преданию, святой Варнава первым из апостолов отправился в Италию проповедовать там слово Божие. Был он в Риме, основал Церковь в городе Медиолане (Милане) и был поставлен в епископы Медиоланской Церкви. Затем, возвратясь на родину, остров Кипр, продолжил распространять там слово Божие.
На 76-м году жизни святой Варнава сподобился принять мученическую кончину. Ревностная проповедь его в главном городе острова Кипра — Саламине восстановила против него живших там иудеев, которые решили убить его. Святой Варнава, предвидя свою кончину, созвал верующих, преподал им последнее наставление и простился с ними. При этом он поручил племяннику своему, апостолу Марку, рассказать обо всем святому апостолу Павлу и завещал положить с собой в гроб Святое Евангелие от Матфея, которое некогда переписал сам и с которым никогда не разлучался. После этого святой апостол Варнава, приобщившись Святых Таин Христовых, явился безбоязненно в собрание иудейское и начал проповедовать там о Христе неверным иудеям. Озлобленные иудеи бросились на святого апостола, вывели его за город, побили камнями и, не довольствуясь этим, решили предать святое тело сожжению. Но тело святого Варнавы осталось цело и невредимо и было похоронено апостолом Марком. Убив святого Варнаву, иудеи начали преследование всех последователей Христа. Верующие разбежались, и место, где был похоронен Апостол, стало неизвестным. Впоследствии, когда вера Христова распространилась уже по всему Кипру, чудеса и исцеления от мощей святого Варнавы открыли то место, где пребывали его святые останки.