Дело святой миссии на Кипре продолжил апостол Варнава, вернувшийся в 50 году на Кипр вместе со своим племянником Марком, сыном сестры Марии (по преданию, в ее доме в Иерусалиме совершились Тайная Вечеря и Сошествие Святого Духа). Сильное противодействие апостолу Варнаве оказали иудеи. Во время его проповеди в Саламинской синагоге они схватили его и за стенами города побили камнями. Тело его было взято апостолом Марком и похоронено западнее Саламина. На грудь Апостола святой Марк положил Евангелие от Матфея. Время кончины апостола Варнавы относят к 57 году
[416]. Полная христианизация населения острова относится к началу V века.Церковным центром Кипра со времен святого Константина Великого был г. Саламин, который после разрушения в результате землетрясения был восстановлен императором Констанцием и назван в его честь Констанцией. Во время завоевания острова арабами г. Констанция был разрушен, и резиденция Архиепископа после возвращения киприотов с Геллеспонта в VIII в. была перенесена в Аммохост (Арсиной, ныне Фамагуста). С тех пор Архиелископ стал подписываться в официальных документах не как Констанцский, а «милостью Божией Архиепископ Кипрский». В начале XIII в. (1215) Архиепископская кафедра волей латинян была перенесена в Левкосию.
Насколько была организованной Кипрская Церковь в первые века видно уже из того, что в Первом Вселенском Соборе участвовали три кипрских епископа: Кирилл Пафский, Геласий Саламинский и Спиридон Тримифунтский. А в деяниях Собора, бывшего в Сердике (343), значатся подписи 12 епископов с о. Кипр, хотя названия их епископий, к сожалению, не отмечены. Блаженный Иероним и Феофил, Архиепископ Александрийский, писавший около 400 г. к жителям Кипра, упоминал имена 15 епископов. Епископы с о. Кипр активно участвовали в деяниях Второго, Третьего и последующих Вселенских Соборов.
Особенно деятельное участие проявила Кипрская Церковь в защите иконопочитания во время иконоборческой ереси. Заслуживают упоминания как поборники иконопочитания епископы констанцские Георгий и Константин. Первый из них за ревностную защиту почитания икон был осужден вместе со святым Иоанном Дамаскином и Патриархом константинопольским Германом на иконоборческом соборе 754 года; второй — был участником Седьмого Вселенского Собора (787), восстановившего справедливость иконопочитания и вместе с тем упразднившего анафематствования собора 754 года на защитников почитания святых икон.
Принимая активное участие в деяниях Вселенских Соборов, архипастыри Кипрской Церкви занимались и просветительной работой у себя на острове. Стремясь обратить в христианство язычников, они были вынуждены одновременно вести и борьбу с возникшим во II столетии гностицизмом. Преследуемые римскими правителями гностики вместе с христианами бежали на Кипр, где нашли, главным образом среди язычников, благоприятную почву для утверждения своих идей. Против этих лжеучителей выступил Саламинский епископ святой Епифаний, оставивший после себя много назидательных сочинений. Из других церковных писателей древнейшего периода Кипрской Православной Церкви необходимо упомянуть Кирилла Пафского, два Слова которого (на Богоявление и о Воплощении Господа) Патриарх Фотий сохранил в своей «Библиотеке», и Трифиллия, епископа Лидраского, которого блаженный Иероним считает «самым красноречивейшим из своих современников и самым знаменитым при императоре Констанции»
[417]. В VI–VII вв. кипрские иерархи писали, главным образом, агиографические труды. Так, Архиепископ Аркадий I написал Житие святого Симеона Столпника, епископ Пафский Феодор — Житие святителя Спиридона Тримифунтского, епископ Тримифунтский Феодор — Житие святителя Иоанна Златоуста. В начале XIII в. святой Неофит Затворник оставил немало бесед, толкований на книги Священного Писания, похвальных слов святым, особенно кипрским; сохранилось и его знаменитое творение «О бедствиях в кипрской стране», в котором он говорит о неустройствах на Кипре в годы правления Исаака Комнина и во время насильственных действий на острове латинян.В так называемый византийский период истории Кипрской Православной Церкви (до 1191) на острове развивалась и монашеская жизнь. Это развитие шло по двум направлениям монашеского подвига — отшельническое монашество и общежительное. Мать святого Константина Великого святая равноапостольная царица Елена спустя год после Первого Вселенского Собора приехала на остров и основала здесь Ставровунийский (Крестовоздвиженский) монастырь. К тому же времени относится и основание монастыря святителя Николая. В конце V века Архиепископ Анфим основал возле г. Саламина монастырь во имя – святого апостола Варнавы. В VII в. упоминается Знаменский монастырь. В житии святого Димитриана говорится о монастыре святого Антония, находящемся около Хитр (IX в.), и др. Некоторые из основанных в тот период монастырей существуют по сей день.