Na soborze nicejskim I Kościół cypryjski był reprezentowany przez kilku biskupów.
Za moment decydującego rozprzestrzenienia się chrześcijaństwa na Cyprze uznaje się IV wiek i okres sprawowania urzędu arcybiskupa Salaminy (następnie Konstancji) przez św. Epifaniusza. W tym samym stuleciu chrześcijaństwo stało się religią panującą w regionie, zastępując kult Apolla. W 431 sobór efeski ogłosił Kościół Cypru autokefalicznym, wbrew stanowisku patriarchy Antiochii.
W VII–IX w., w czasie najazdów arabskich na Cypr, Kościół Cypryjski poniósł znaczne straty. W 691, po zniszczeniu Konstancji, Kurion i Pafos arcybiskup Jan przeniósł swoją siedzibę do Hellespontu; miejsce to otrzymało następnie nazwę Nowej Justyniany. Po odparciu Arabów hierarchowie cypryjscy obrali na stałą siedzibę Arsinoe i Ammochostos, w miejsce całkowicie zniszczonej Konstancji. Zachowali jednak tytuł arcybiskupów Nowej Justyniany i całej Cypru.
Frankokracja i panowanie weneckie Po wielkiej schizmie wschodniej Kościół Cypru zerwał kontakty z Kościołem łacińskim.