Από της ιδρύσεως της η Εκκλησία της Κύπρου από τους Αποστόλους Παύλο και Πέτρο με την χειροτονία και την εγκατάσταση των πρώτων επισκόπων, λειτουργούσε αυτόνομα, αντιμετώπιζε όλα τα προβλήματα που προέκυπταν χωρίς τη παρέμβαση από καμιά Εκκλησία, εξέλεγε και χειροτονούσε τους επισκόπους της, δηλαδή είχε πλήρη αυτοδιοίκηση, με ανώτατη αρχή τη σύνοδό της.
Αυτή η τακτική ήταν σύμφωνη με την παράδοση της Εκκλησίας και τους κανόνες της Α΄ Οικουμενικής συνόδου.
Στις αρχές του πέμπτου αιώνα, η Εκκλησία της Αντιόχειας, θέλησε να αμφισβητήσει αυτή την αρχή και να θελήσει να επιβάλει τον έλεγχό της στην Εκκλησία της Κύπρου, υποστηρίζοντας ότι, αφού η Κύπρος διοικητικά υπάγεται στην Αντιόχεια, έπρεπε και η Εκκλησία της να υπαχθεί σ’αυτή και οι χειροτονίες των επισκόπων της Κύπρου να γίνονται από την Εκκλησία της Αντιόχειας.

Στη προσπάθεια αυτή των επισκόπων της Αντιόχειας, αντέδρασαν οι ιεράρχες της Κύπρου και έφεραν το θέμα για συζήτηση στη Γ΄ Οικουμενική σύνοδο στην Έφεσο το 431 μ.Χ. Στη σύνοδο οι κύπριοι ιεράρχες με τα επιχειρήματά τους έπεισαν για το σύστημα αυτοδιοίκησης της Εκκλησίας της Κύπρου που επικρατούσε από της ιδρύσεώς της και ζήτησαν όπως κατοχυρωθεί και επισήμως το αυτοκέφαλο, κάτι που έγινε με τον όγδοο κανόνα της συνόδου.

Δυστυχώς η αμφισβήτηση εκ μέρους της Εκκλησίας της Αντιόχειας, έφερε και πάλι το θέμα στο προσκήνιο πενήντα χρόνια αργότερα, υποστηρίζοντας ότι οι κύπριοι όφειλαν τον εκχριστιανισμό τους στην Εκκλησία Αντιόχειας και σ'αυτή τους τη θέση είχαν συμπαραστάτη τον αυτοκράτορα Ζήνωνα.
Θεία βουλήση, ο Απόστολος Βαρνάβας παρουσιάστηκε στον ύπνο του Αρχιεπισκόπου Ανθέμιου και τον συμβούλευσε να μεταβεί στην Κωνσταντινούπολη και να ενημερώσει προσωπικά τον αυτοκράτορα Ζήνωνα για την όλη κατάσταση. Για ενίσχυση του Ανθέμιου, ο Απόστολος Βαρνάβας του φανέρωσε και τον τόπο που βρισκόταν ο τάφος του. Ο Αρχιεπίσκοπος Ανθέμιος έσκαψε στο μέρος που του υπέδειξε ο Απόστολος και όντως βρήκε το ιερό λείψανό του με το κατά Ματθαίο Ευαγγέλιο να βρίσκεται στο στήθος του.

Ο Ανθέμιος παίρνοντας μαζί του και το κατά Ματθαίο Ευαγγέλιο, πήγε στην Κωνσταντινούπολη και συνάντησε τον αυτοκράτορα Ζήνωνα στον οποίο δώρισε το Ευαγγέλιο, τον ενημέρωσε για το λείψανο του Αποστόλου Βαρνάβα γεγονός που μαρτυρούσε την ίδρυση της Εκκλησίας μας από τους Αποστόλους και όχι από την Εκκλησία της Αντιόχειας, ανέλυσε την όλη κατάσταση και τον έπεισε για το δίκαιο της θέσης της Εκκλησίας της Κύπρου.
Η προσπάθεια αυτή του Αρχιεπισκόπου Άνθιμου έφερε και το ποθητό αποτέλεσμα, με προτροπή του αυτοκράτορα, συνεκλήθη η σύνοδος η οποία επαναβεβαίωσε την απόφαση της Γ΄ Οικουμενικής συνόδου για το αυτοκέφαλο της Εκκλησίας της Κύπρου. Την απόφαση αυτή της συνόδου επικύρωσε ο αυτοκράτορας και επί πλέον παρεχώρησε για τον εκάστοτε Αρχιεπίσκοπο Κύπρου και τα αυτοκρατορικά προνόμια, να υπογράφει με κόκκινο μελάνι, να κρατεί αυτοκρατορικό σκήπτρο και να φορεί κατά τις ιεροτελεστίες πορφυρό μανδύα.