Barnabas, born Joseph (Ἰωσήφ) or Joses (Ἰωσής), was according to tradition an early Christian, one of the prominent Christian disciples in Jerusalem. According to Acts 4:36, Barnabas was a Cypriot Jew. Named an apostle in Acts 14:14, he and Paul the Apostle undertook missionary journeys together and defended Gentile converts against the Judaizers. They traveled together making more converts, and participated in the Council of Jerusalem. Barnabas and Paul successfully evangelized among the "God-fearing" Gentiles who attended synagogues in various Hellenized cities of Anatolia.

The Church of Cyprus is one of the autocephalous Greek Orthodox churches that together with other Eastern Orthodox churches form the communion of the Eastern Orthodox Church. It is one of the oldest Eastern Orthodox autocephalous churches; it claims to have always been independent, although it may have been subject to the Church of Antioch before its autocephaly was recognized in 431 at the Council of Ephesus. The bishop of the ancient capital, Salamis was constituted metropolitan by Emperor Zeno, with the title archbishop.