Šv. Paulius, Konstantinopolio arkivyskupas, buvo išrinktas patriarchu po patriarcho Aleksandro mirties († 340), kai vėl įsiplieskė arijonų erezija. Susirinkime, kuriame buvo išrinktas naujasis Konstantinopolio patriarchas, dalyvavo daug arijonų. Jie aršiai maištavo prieš Pauliaus išrinkimą, tačiau tuomet Tarybos narių daugumą sudarė stačiatikiai. Tuometinis imperatorius Konstancijus, valdęs rytinę Romos imperijos dalį, buvo arijonas. Tuo metu, kai buvo renkamas patriarchas, jo nebuvo Konstantinopolyje. Grįžęs jis sušaukė susirinkimą, kuris neteisėtai paskelbė šventąjį Paulių kaip nušalintą, imperatorius išvijo jį iš sostinės. Į šventojo vietą buvo išrinktas arijonas Euzebijus iš Nikomedijos. Patriarchas Paulius pasitraukė į Romą, kur prieglobstį rado kiti Euzebijaus išvaryti stačiatikių vyskupai.
Euzebijus neilgai vadovavo Bažnyčiai. Jam mirus, šventasis Paulius grįžo į Konstantinopolį. Jo kaimenė pasitiko išpažinėją išskėstomis rankomis. Tačiau Konstancijus ištrėmė šventąjį antrą kartą, ir jam teko grįžti į Romą. Vakarų imperatorius Konstantas parašė savo Rytų bendravaldžiui Konstancijui grasinantį laišką, kurį šis kartu su ištremtu šventuoju arkivyskupu išsiuntė į Konstantinopolį. Grasinimai suveikė, ir šventasis Paulius buvo grąžintas į patriarcho sostą.
Ilgai netrukus pamaldusis imperatorius Konstantas, stačiatikių gynėjas, buvo klastingai nužudytas per rūmų perversmą. Šventasis Paulius vėl buvo ištremtas iš sostinės ir išsiųstas į tremtį Armėnijoje, Kukuzo mieste, kur mirė kankinio mirtimi. Patriarchui celebruojant dieviškąją liturgiją, į šventovę įsiveržė arijonai ir uždusino šventąjį jo hierarchiniu omoforionu. Tai įvyko 350 metais.
381 m. šventasis karalius Teodosijus Didysis iškilmingai pergabeno šventojo Pauliaus Išpažinėjo relikvijas iš Kukuzo į Konstantinopolį. 1326 metais šventojo Pauliaus relikvijos buvo perkeltos į Veneciją.
Šventasis Atanazas Didysis, šventojo Pauliaus amžininkas, trumpai rašo apie jo tremtį: „Šventasis Paulius pirmą kartą Konstancijaus buvo ištremtas į Pontą, antrą kartą Konstancijaus surakintas geležiniais pančiais, įkalintas Singaroje Mesopotamijoje, iš ten perkeltas į Emesą, o ketvirtą kartą – į Kukuzą Kapadokijoje prie Tauro dykumų“.
