Salamina era un'antica città cipriota, sede del metropolita della Chiesa autocefala di Cipro. Distrutta da un terremoto attorno al 340, la città fu ricostruita e chiamata Costanza (Constantia) in onore dell'imperatore Costanzo II; infine fu definitivamente distrutta nel 647 dagli Arabi. Per questo motivo, il metropolita spostò la sua sede a Famagosta, mantenendo il titolo di Salamina-Costanza, fino all'arrivo degli eserciti crociati alla fine del XII secolo. Con l'istituzione delle diocesi latine nell'isola, il metropolita fu relegato ad un ruolo marginale e confinato in Carpasia. In seguito alla conquista ottomana dell'isola, i metropoliti trasferirono la loro sede a Nicosia, che era stata la capitale cipriota durante la dominazione latina. Il Santo Sinodo della Chiesa cipriota nel 2007 ha restaurato la diocesi di Costanza-Famagosta (Costantia-Ammochostos), ripristinando così dopo otto secoli la sede che fu dell'apostolosan Barnaba.