Миссионерскую деятельность апостолы начали в Саламисе, где проповедовали в местных синагогах. Путешествуя по всему острову, Павел, Варнава и Иоанн Марк пришли в г. Пафос[4], где столкнулись с правителем Кипра, римским проконсулом Сергием Павлом, который очень хотел послушать их проповедь. Он был обращен в новую веру с помощью чуда, которое сотворил апостол Павел, ослепив Елима волхва (Деян. 13, 6-12). Возможно, это один из замечательных эпизодов в долгой истории острова. Этим обращением ознаменовалось начало проникновения новой веры в среду римской администрации, и это первый случай, когда знатный римлянин принял христианство. Одновременно появилась Кипрская апостольская церковь и стала одной из предвестниц христианства по всему миру.
После посещения Кипра Иоанн Марк возвратился в Иерусалим, а апостолы Павел и Варнава проповедовали в Памфилии, Антиохии, Иконии, Ликаонии. Однажды апостолы решили посетить братьев в тех землях, где они были с миссией. Варнава, опять взяв с собой Иоанна Марка, отплыл на Кипр. Второе прибытие на родной остров было в 50 г. Они вновь путешествовали по острову, Варнава рукоположил во епископы наиболее достойных из тех, кто был обращен в новую веру в первое его посещение, приобщал к христианству других. У одних апостолы находили гостеприимство, у других – откровенную враждебность, особенно со стороны иудеев, подстрекаемых своими вождями. Именно от них Варнава принял мученическую смерть. История его кончины такова. Апостол Варнава, будучи в Саламисе, обычно ходил для проповеди в синагогу, где раньше находил некоторое понимание среди сирийских иудеев. Но это продолжалось недолго. Однажды, войдя туда по обыкновению в субботу, он заметил перемену в отношении к нему, что не предвещало доброго. В тот день он, как обычно, беседовал с иудеями. В день смерти, после евхаристии, он вошел в синагогу. Предвидев, что погибнет, Варнава дал распоряжение своему племяннику и сподвижнику Иоанну Марку о погребении и попросил его затем уехать в г. Эфес (Малая Азия) к апостолу Павлу. Иудеи внезапно вскочили, схватили его и поволокли в помещение, примыкающее к синагоге. В ту же ночь они забили его камнями, намереваясь потом сжечь. Но Иоанн Марк тайно перенес тело в пещеру к западу от Саламиса. После смерти Варнавы начались преследования христиан, и сведения о месте погребения апостола были утрачены до тех пор, пока сам Святой не явился в правление византийского императора Зенона (474–491)[5].
Обращение Кипра в новую веру было нелегкой задачей. Здесь жили этнические греки-язычники, они верили в древних римских богов. Еще при Птолемеях на Кипре поселились иудеи, исповедовавшие иудаизм. Положение осложнилось, когда количество иудеев, живущих на Кипре, увеличилось с их притоком после 70 г., когда Иерусалим был разрушен при римском императоре Тите (79–81). В 116 г. распространение христианства на Кипре повлекло уничтожение большого количества населения. Именно в этом году иудеи в Саламисе подняли восстание, в результате тысячи греков были убиты. За этим последовали массовые убийства иудеев в отмщение. По историческим сведениям, в результате погибло 240 000 человек. Скорее всего, это преувеличение, но иудеям было запрещено поселяться на Кипре, хотя известно о существовании синагог на Кипре и в более позднее время. Большинство греков твердо придерживались культа древних богов, но новая вера постепенно утверждалась.