He was a native of Thessalonica, a presbyter of Constantinople, and secretary to the aged bishop Alexander of Constantinople, his predecessor in the see. No sooner had Alexander breathed his last the Arian and Orthodox parties came into open conflict. The orthodox party prevailed; Paulus was elected and consecrated by bishops who happened to be at Constantinople in the Church of Peace, close to what was afterwards the Great Church of Saint Sophia.
The emperor Constantius II had been away during these events. On his return he was angry at not having been consulted. He summoned a synod of Arian bishops, declared Paulus quite unfit for the bishopric, banished him, and translated Eusebius of Nicomedia to Constantinople. This is thought to have been in 338; Eusebius died in 341. Paulus was at once restored by the people to his see; however the Arians seized the occasion; Theognis of Nicaea, Theodorus of Heraclea, and other heterodox bishops, consecrated Macedonius in the church of St. Paul; and again the city became the prey of a civil war.
The emperor was at Antioch when he heard of this, where he ordered Hermogenes, his general of cavalry, to see that Paulus was again expelled. The people would not hear of violence being done to their bishop; they rushed upon the house where the general was, set fire to it, killed him on the spot, tied a rope round his feet, pulled him out from the burning building, and dragged him in triumph round the city.
Constantius was not likely to pass over this rebellion against his authority. He rode on horseback at full speed to Constantinople, determined to make the people suffer heavily for their revolt. They met him, however, on their knees with tears and entreaties, and he contented himself with depriving them of half their allowance of corn, but ordered Paulus to be driven from the city.
Athanasius of Alexandria was then in exile from Alexandria, Marcellus from Ancyra, and Asclepas from Gaza; with them Paulus betook himself to Rome and consulted Pope Julius I, who examined their cases severally, found them all staunch to the creed of Nicaea, admitted them to communion, espoused their cause, and wrote strongly to the bishops of the East. Athanasius and Paulus recovered their sees; the Eastern bishops replied to Pope Julius altogether declining to act on his advice.
Constantius was again at Antioch, and as resolute as ever against the choice of the people of Constantinople. Philippus, prefect of the East, was there, and was ordered to once more expel Paulus and to put Macedonius definitely in his place. Philippus was not ready to incur the risks and fate of Hermogenes; he said nothing about the imperial order.
At a splendid public bath called Zeuxippus, adjoining a palace by the shore of the Hellespont, Philippus asked bishop Paulus to meet him, as if to discuss some public business. When Paulus arrived, he showed him the emperor's letter, and ordered him to be quietly taken through the palace to the waterside, placed on board ship, and carried off to Thessalonica, his native town. Philippus allowed him to visit Illyricum and the remote provinces, but forbade him to set foot again in the East.
List of Constantinople patriarchs
Eusebius of Nicomedia and later Macedonius I