Urodził się na Cyprze w rodzinie żydowskiej z pokolenia Lewiego. Jego właściwe imię było Józef, ale Apostołowie dali mu przydomek Barnaba. Według Klemensa Aleksandryjskiego i Euzebiusza miał należeć do 72 uczniów Jezusa.

Był krewnym św. Marka Ewangelisty, dlatego św. Paweł nazywa go kuzynem Ewangelisty (Koi 4,10). Św. Barnaba zapewne ze św. Pawłem przybył do Jerozolimy, aby u stóp Gamaliela, znanego uczonego żydowskiego, pogłębiać wiedzę o religii mojżeszowej. Dzieje Apostolskie tak wprowadzają nas w działalność św. Barnaby:
Józef, nazwany przez Apostołów Barnaba, to znaczy „Syn Pocieszenia", lewita rodem z Cypru, sprzedał ziemię, którą posiadał, a pieniądze przyniósł i złożył u stóp Apostołów (Dz 4,36-37).
O powadze, z jaką traktowali go Apostołowie, świadczy to, że św. Paweł po nawróceniu udał się najpierw do Barnaby, by pośredniczyć pomiędzy nim a Apostołami:
Kiedy [Paweł] przybył do Jerozolimy, próbował przyłączyć się do uczniów, lecz wszyscy bali się go, nie wierząc, że jest uczniem. Dopiero Barnaba przygarnął go i zaprowadził do Apostołów, i opowiedział im, jak w drodze [Szawel] ujrzał Pana, który przemówił do niego, i z jaką silą przekonania przemawiał w Damaszku w imię Jezusa. Dzięki temu przebywał z nimi i w Jerozolimie. Przemawiał też i rozprawiał z hellenistami, którzy usiłowali go zgładzić. Bracia jednak dowiedzieli się o tym, odprowadzili go do Cezarei i wysiali do Tarsu (Dz 9,26-30).

Wraz ze św. Pawłem udał się do Antiochii również św. Barnaba. Pozyskali tam wielką liczbę ludzi dla Chrystusa. W Antiochii też po raz pierwszy nazwano uczniów chrześcijanami (Dz 11,26). Był to rok 42 po narodzeniu Chrystusa. Św. Barnaba i św. Paweł swoje nauczanie kierowali najpierw do Żydów. Kiedy ci ich odrzucili, poszli do pogan. Aby jednak neofitów z pogaństwa nie zrazić, nie nakładano na nich żadnych obowiązków z prawa mojżeszowego, a żądano jedynie, by dawali świadectwo Chrystusowi przez przyjęcie chrztu świętego i życie ewangeliczne. Doszło to jednak do gminy jerozolimskiej, która pilnie dotąd przestrzegała prawa mojżeszowego. Wezwani do Jerozolimy św. Barnaba i św. Paweł bronili swojego stanowiska wobec nawróconych z pogaństwa. Ich stanowczymi przeciwnikami byli natomiast nawróceni Żydzi.