Святитель Павел, архиепископ Константинопольский, был избран на патриаршую кафедру после смерти патриарха Александра († 340), когда вновь вспыхнула арианская ересь. На Соборе, избиравшем нового Константинопольского патриарха, присутствовало много ариан. Они восставали против избрания святителя Павла, но православных членов Собора оказалось большинство. Император Констанций, царствовавший над Восточной половиной Римской империи, был арианин. Во время выборов патриарха его не было в Константинополе. По возвращении своем он созвал собор, который незаконно объявил низложенным святителя Павла, и император изгнал его из столицы. На место святителя возвели арианина Евсевия Никомидийского. Патриарх Павел удалился в Рим, где нашли себе приют и другие православные епископы, изгнанные Евсевием.
Недолго управлял Церковью Евсевий. Когда он умер, святитель Павел вернулся в Константинополь. Он с любовью был встречен паствой. Но Констанций вторично изгнал святого, и ему пришлось возвратиться в Рим. Император Констант написал своему восточному соправителю Констанцию грозное письмо, которое отправил в Константинополь со святым архипастырем-изгнанником. Угрозы подействовали, и святитель Павел был возвращен на патриарший престол.
Однако вскоре благочестивый император Констант, защитник православных, был предательски убит во время дворцового переворота. Святителя Павла вновь изгнали из столицы и отправили в ссылку в Армению, в город Кукуз, где он принял мученическую кончину. Когда патриарх совершал Божественную литургию, ворвались ариане и задушили святого его святительским омофором. Произошло это в 350 году.
В 381 году святой царь Феодосий Великий торжественно перенес мощи святителя Павла исповедника из Кукуза в Константинополь. В 1326 году мощи святителя Павла перенесены в Венецию.
Святитель Афанасий Великий, современник святого Павла, об его изгнании пишет кратко: "Святой Павел в первый раз сослан Константином в Понт, во второй раз Констанцием, окованный железными узами, заточен в Сингару Месопотамскую и оттуда переведен в Емесу, а в четвертый раз в Кукузу Каппадокийскую у Таврских пустынь".
