После кончины Лазарь был похоронен в месте, получившем впоследствии название «Ларнаке» , что в переводе с греческого языка означает «гроб». Известный г. Ларнака получил название в честь гроба свт. Лазаря.
О местонахождении гроба Святого и его мощей не было известно в течение нескольких столетий. После обретения их в 898 г. по приказу византийского императора Льва VI Мудрого (886–912) мощи должны были быть перенесены в Константинополь, но туда отправили лишь часть их. Сами мощи были погребены в саркофаге, на месте погребения Лев VI воздвиг церковь в его честь. В 1571 г., когда при захвате острова города разрушались турками до основания, мощи вывозились с Кипра или прятались в укромных уголках острова, и тогда мощи свт. Лазаря опять надолго исчезли. Второе их обретение произошло в 1972 г.
Когда столица Римской империи была перенесена в Константинополь и была основана Византийская империя, Кипр был включен в состав префектуры Востока[9]
, главным городом которой была Антиохия. Хотя остров потерял политическую автономию, которая была у него со времен римских императоров, церковь оставалась независимой от Антиохии.Как и во времена римского правления, Кипр стал объектом внимания византийских императоров. Первым проявлением такого интереса было посещение его в 327 г. императрицей Еленой, матерью первого христианского императора Константина Великого.