In 478, the grave of St. Barnabas was found, with a copy of the [[Gospel of Matthew]] on his [[relics]]. The autocephaly of the Church of Cyprus was confirmed later that year by the Roman Emperor [[Zeno (emperor)|Zeno]] who granted its Archbishop "three privileges," that is: to sign his name in ''cinnabar'', to wear purple instead of black under his [[vestments]], and to use an imperial scepter instead of the episcopal [[crosier]].

The Arab invasions of the seventh century forced the Archbishop to flee the island to Hellespont, where under the protection of Emperor [[Justinian II]] he established a new city called Nova Justiniana (now "Nea Justiniana") in honor of the emperor. In 698, the Arabs were driven out of Cyprus and the Archbishop returned to the island, but retained the title of Archbishop of Nova Justiniana and All Cyprus. With the occupation of Cyprus by the Crusades from 1191 to 1571, the Orthodox hierarchy found itself subordinated to the occupying Latin French and Venetian kings, who forced a reduction in the number of Orthodox bishops from 14 to four. Additionally, the Latin bishops attempted to gain concessions on the differences in doctrine and practices between the two churches.