Με την ίδρυση του Ανατολικού (Βυζαντινού) Ρωμαϊκού κράτους, η Κύπρος υπήχθη σ' αυτό και παρέμεινε για πολύ ακόμη διάστημα ενταγμένη στη διοίκηση της Ανατολής με έδρα την Αντιόχεια της Συρίας. Λόγω αυτού του στενού δεσμού της με την Αντιόχεια, η Κύπρος βρέθηκε στον κύκλο επιρροής της μεγαλούπολης αυτής της Συρίας και του ελληνιστικού πολιτισμού της, αλλά ενεπλάκη και στις επεκτατικές φιλοδοξίες των επισκόπων/πατριαρχών της, όπως ήδη ανεφέρθη πιο πάνω (βλέπε επίσης λήμμα Βυζάντιο και Κύπρος). Ωστόσο με το γνωστό «θαύμα» της ανεύρεσης του λειψάνου του αποστόλου Βαρνάβα και του ιερού ευαγγελίου από τον Κύπριο αρχιεπίσκοπο Ανθέμιο*, που εντυπωσίασε την Κωνσταντινούπολη, η Εκκλησία της Κύπρου μπόρεσε ν' αποκρούσει τις βλέψεις εκείνης της Αντιόχειας και να καταστεί αυτοκέφαλη.
Οι εκκλησιαστικές σχέσεις της Κύπρου με την Εκκλησία της Συρίας ήταν ιδιαίτερα στενές, ακόμη και μετά την απόσπαση του νησιού από τη διοίκηση της Ανατολής και υπαγωγή του αλλού, κατά τον 6ο μ.Χ. αιώνα. Οι σχέσεις αυτές δεν εκφράζονται μόνο με τη συμμετοχή της Εκκλησίας της Κύπρου σε εκκλησιαστικές συνόδους αλλά και με πάρα πολλούς άλλους τρόπους, περιλαμβανομένων και διαφόρων αιρέσεων που εισήχθησαν στο νησί από τη Συρία. Εξ άλλου οι εκκλησιαστικές αυτές σχέσεις με το πατριαρχείο Αντιοχείας θα συνεχιστούν για πολλούς αιώνες, μέχρι και τα νεότερα ακόμη χρόνια۠ μάλιστα και αρκετοί Κύπριοι θα αναλάβουν ύψιστα ιεραρχικά αξιώματα κατά καιρούς στο πατριαρχείο Αντιοχείας, ενώ σε διάφορες περιπτώσεις ιεράρχες του πατριαρχείου αυτού θα διαδραματίσουν ρόλους στις κυπριακές εξελίξεις διαφόρων εποχών. Από τη Συρία και την Παλαιστίνη εξάλλου (όπως και από το Σινά, τη Μικρά Ασία και την Αίγυπτο), θα υπάρξει κι ένα μακρύ και αδιάκοπο ρεύμα ασκητών προς την Κύπρο, που εκφράζεται και με τον θρύλο των 300 «Αλαμάνων»* αγίων της Κύπρου οι οποίοι υποτίθεται ότι ήλθαν στο νησί από την Παλαιστίνη (βλέπε και λήμμα Εκκλησία Κύπρου).
Ακολούθησαν οι αιώνες των αραβικών επιδρομών (7ος-10ος) που έπληξαν καίρια την Κύπρο. Η προώθηση των Αράβων στις χώρες απέναντι από την Κύπρο είχε μεταξύ άλλων και αποτέλεσμα τη φυγή Χριστιανών από τη Συροπαλαιστίνη και καταφυγή-εγκατάστασή τους στην Κύπρο (όπως η πιθανή άφιξη στο νησί των κατοίκων της Αράδου, πόλης επί της Συροπαλαιστινιακής ακτής, στα μέσα του 7ου αιώνα). Σύροι από την Μπαάλμπεκ, προφανώς εξισλαμισθέντες Χριστιανοί, εγκαταστάθηκαν επίσης σε ειδική «πόλη» κοντά στην Πάφο, μαζί με φρουρά από 12.000 Άραβες τον 7ο αιώνα. Ακόμη, ύστερα από συνθήκη μεταξύ Βυζαντινών και Αράβων, τον κρίσιμο 7ο αιώνα εγκαταστάθηκαν στην Κύπρο και σώματα Μαρδαϊτών (Βυζαντινών ορεσίβιων πολεμιστών). Οι Μαρδαΐτες* αυτοί αποσύρθηκαν από την περιοχή του Λιβάνου και αρκετούς έστειλαν οι Βυζαντινοί στην Κύπρο, ιδίως στην περιοχή Μόρφου, όπου εισήγαγαν και τη λατρεία του προστάτη τους αγίου Μάμα. Ωστόσο αναφέρεται, στα τέλη του 7ου αιώνα, και μεταφορά κι εγκατάσταση Κυπρίων στη Συρία (μετά τη μεταφορά, από τους Βυζαντινούς, Κυπρίων στον Ελλήσποντο, και πιθανότατα ως αραβικό αντίποινο σ' αυτήν). Λίγο όμως αργότερα οι Κύπριοι άποικοι επέστρεψαν στο νησί τους, τόσο από τη Συρία όσο και από τον Ελλήσποντο. Στο μεταξύ η εξάπλωση των Αράβων έφθασε μέχρι σ' ολόκληρη τη Συροπαλαιστίνη, οι δε Συροπαλαιστινιακές ακτές είχαν καταστεί το ορμητήριο των αλλεπάλληλων καταστροφικών αραβικών επιδρομών κατά της Κύπρου (βλέπε λήμμα Αράβων επιδρομές). Η επικράτηση των Αράβων στη Συροπαλαιστίνη ώθησε νέο κύμα μοναχών και άλλων Χριστιανών ιερωμένων να καταφύγει στην Κύπρο. Από την άλλη, σε μερικές περιπτώσεις (όπως από τον Βυζαντινό ναύαρχο Ιμέριο*), η Κύπρος χρησιμοποιήθηκε ως ορμητήριο των Βυζαντινών κατά της αραβοκρατούμενης Συροπαλαιστίνης.
Νέα εντελώς κατάσταση δημιουργήθηκε στην Ανατολική Μεσόγειο με την έναρξη των Σταυροφοριών και την ίδρυση (ήδη με την πρώτη Σταυροφορία) των Λατινικών κρατιδίων στη Συροπαλαιστίνη και ακόμη την ίδρυση του βασιλείου των Ιεροσολύμων. Με την τρίτη Σταυροφορία, η Κύπρος κατελήφθη και αυτή από τον βασιλιά της Αγγλίας Ριχάρδο και στη συνέχεια οργανώθηκε σε φράγκικο βασίλειο.
Πριν καταληφθεί από τους Σταυροφόρους, η Κύπρος δέχθηκε καταστροφικές επιδρομές κατά τα τέλη της Βυζαντινής περιόδου της ιστορίας της, μεταξύ των οποίων και η ιδιαίτερα εγκληματική επιδρομή του Σταυροφόρου «ευγενούς» Ρενώ (Ρεϋνάλδου) ντε Σιατιγιόν* του πριγκιπάτου της Αντιόχειας, στα 1155, ενώ ακολούθησε, στα 1161, επιδρομή άλλου «ευγενούς», του Ραϋμόνδου Γ' της Τριπόλεως. Έτσι, λίγο μετά την ίδρυση των σταυροφορικών κρατιδίων και ηγεμονιών στη Συρία, η Κύπρος επλήγη καίρια απ' εκεί, μέχρι που και η ίδια κατελήφθη (το 1191) από τους Σταυροφόρους του Ριχάρδου Λεοντόκαρδου.