Saint Paul the Confessor, Archbishop of Constantinople, was chosen to the patriarchal throne after the death of Patriarch Alexander (+ 340), when the Arian heresy had again flared up. Many of the Arians were present at the Council which selected the new Archbishop of Constantinople. They revolted in opposition to the choice of St Paul, but the Orthodox at the Council were in the majority.
The emperor Constantius, ruling over the Eastern half of the Roman Empire, was an Arian. He was not in Constantinople for the election of the Archbishop, and so it took place without his consent. Upon his return, he convened a council which illegally deposed St Paul, and the emperor banished him from the capital. In place of the saint they elevated Eusebius of Nicomedia, an impious heretic. Archbishop Paul withdrew to Rome, where other Orthodox bishops were also banished by Eusebius.
Eusebius did not rule the Church of Constantinople for long. When he died, St Paul returned to Constantinople, and was greeted by his flock with love. But Constantius exiled the saint a second time, and so he returned to Rome. The Western emperor Constans wrote a harsh letter to his Eastern co-ruler, which he sent to Constantinople along with the holy exiled archpastor. The threats worked, and St Paul was reinstated upon the archepiscopal throne.
But soon the pious emperor Constans, a defender of the Orthodox, was treacherously murdered during a palace coup. They again banished St Paul from Constantinople and this time sent him off in exile to Armenia, to the city of Cucusus, where he endured a martyr's death.
When the Archbishop was celebrating the Divine Liturgy, Arians rushed upon him by force and strangled him with his own omophorion. This occurred in the year 350. In 381, the holy Emperor Theodosius the Great solemnly transferred the relics of St Paul the Confessor from Cucusus to Constantinople. In 1326, the relics of St Paul were transferred to Venice.
St Athanasius the Great, a contemporary of St Paul, writes briefly about his exiles, "St Paul the first time was sent by Constantine to Pontus, the second time he was fettered with chains by Constantius, and then he was locked up in Mesopotamian Syngara and from there moved to Emesus, and the fourth time to Cappadocian Cucusus in the Taurian wilderness."
Troparion - Tone 3
For confessing the divine faith,
among her priests the Church has shown you to be another Paul.
Abel cries out to the Lord together with you, as does the righteous blood of Zachariah.
Venerable father, entreat Christ God to grant us His great mercy.
Kontakion - Tone 4
Paul, you shone on the earth like a star of heavenly splendor;
now you enlighten the universal Church for which you suffered,
for you laid down your life,
and your blood cries out to the Lord like that of Zachariah and Abel.