The holy, glorious and all-laudable Apostle Barnabas was born to a wealthy family in the tribe of Levi. Later becoming one of the Seventy Apostles, he studied with Saul (later St. Paul) under Gamaliel. From birth his given name was Joseph, but the Apostles called him Barnabas ("son of consolation") because he was gifted at comforting people's souls. It was St. Barnabas that introduced St. Paul to the other Apostles after his conversion. St. Barnabas was likely the first to preach in Rome and Milan.
He martyred by the Jews on the island of Cyprus and was buried by St. Mark. Many receive healing at his grave, which place was unknown for hundreds of years until the Council of Chalcedon (451) when he appeared to Archbishop Anthemius in a dream and revealed its location. This appearance and the finding of St. Barnabas' miraculous relics is what kept the Patriarch of Antioch from absorbing Cyprus into its jurisdiction and thus this Apostolic Church of Cyprus has since been independent.