Byzantine Period in Cyprus 
   
The first two centuries were peaceful and prosperous. Emperor Constantine of Byzantium had officially recognised Christianity in 313 AD. In the late 4th century AD Emperor Theodosius ordered the closure of all pagan temples. This put an end to the rituals at the Temple of Aphrodite in Paphos, though worship of Aphrodite continued.
   
 
Depicted in this mosaic are Emperor Constantine and his mother Helena carrying the "true cross"
Depicted in this mosaic are Emperor Constantine and his mother Helena carrying the "true cross"

During this period (also known as the Early Byzantine period in Cyprus), Emperor Constantine's mother Helena visited the island in 327 AD on her way from Jerusalem. Also during this period (332 - 333 AD) the island was hit by destructive earthquakes.

This period also saw the discovery of the  tomb of St Barnabas by Archbishop Amthemios who was thought to be led by a vision in his dream. Within the tomb he found the gospel, which according to St Mark, was handwritten by Barnabas. This earned him great fame and privileges (he was allowed to sign papers in Imperial purple ink) and led to Cyprus being granted the status of an independent church in 478 AD.

After the division of the Roman Empire (AD 395) Cyprus remained subject to the Eastern, or Byzantine, empire at Constantinople, being part of the Diocese of the Orient governed from Antioch. In the ecclesiastical matters, however, the Church of Cyprus was autocephalous -i.e., independent of the Patriarchate of Antioch- having been given that privilege in 488 by the emperor Zeno. The Archbishop received the rights, still valued and practiced, of carrying sceptre instead of a crozier and writing his signature in ink of imperial purple.  

    
   

References 

Chronological History