Iosif, numit Barnaba
Cea mai veche mărturie despre Barnaba se află în Faptele Apostolilor. Autorul îl numește Iosif, levit cipriot, iar apostolii îi dau numele Barnaba, explicat în text ca „fiul mângâierii” sau „al încurajării” (Fapte 4, 36). El vinde un ogor și pune banii la dispoziția comunității din Ierusalim. În Fapte 9, 27, Barnaba îl ia pe Saul și îl prezintă apostolilor, când ceilalți se tem încă de fostul persecutor.
Misiunea alături de Pavel
Biserica din Ierusalim îl trimite la Antiohia, unde Barnaba vede înflorirea comunității și îl caută pe Saul în Tars; împreună îi învață pe credincioși un an (Fapte 11, 22–26). Apoi călătoresc în Cipru și în Asia Mică, vestind Evanghelia și întemeind comunități. Fapte 15 consemnează dezacordul lor privind întoarcerea lui Ioan Marcu: Pavel nu voia să-l ia după ce acesta îi părăsise într-o călătorie anterioară, iar Barnaba a plecat cu Marcu spre Cipru. Textul biblic păstrează astfel atât colaborarea lor, cât și o divergență reală între misionari.
Cipru, martiriul și memoria locală
Noul Testament nu povestește moartea lui Barnaba. Tradiția cipriotă spune că s-a întors la Salamina și a fost ucis prin lapidare în jurul anului 62. OCA transmite și tradiția descoperirii mormântului în 448, când arhiepiscopul Antim ar fi aflat în vis locul și o copie a Evangheliei lui Matei așezată pe pieptul sfântului. Aceste episoade aparțin tradiției hagiografice și cultului local, nu relatării canonice a Faptelor. Pomenirea lui este la 11 iunie; mănăstirea și mormântul venerat de lângă Salamina au devenit repere ale identității creștine cipriote.