Leontius was born in Tiberioupolis, on the Balkan frontier of the Byzantine Empire.
He was tonsured a monk in Constantinople, where he lived until he traveled through Patmos, Cyprus, to Crete.
He became the hegumen of the Monastery of Saint John the Theologian in Patmos.
Theodosius Goudelis, an acquaintance and biographer of Leontius, wrote that the Latin patriarch of Jerusalem, Amalric of Nesle, attempted to have Leontius assassinated, which the modern historian Bernard Hamilton considers improbable.
Amalric was, however, hostile to Leontius; and while King Baldwin was anxious that Leontius be treated well in order to win Byzantine protection, Amalric only acquiesced to royal demands so far as to allow Leontius to celebrate the Divine Liturgy in the Church of the Holy Sepulchre in the presence only of the Orthodox canons.