He was elected Patriarch in 537 when the Greek Church of Alexandria, which had previously recognized the Miaphysite Theodosius I, then exiled Gainas.
[1] This election was the final split between the Miaphysite and Orthodox lineage, which lasts until today.
According to Procopius, when Justinian made Paul patriarch, he gave him authority over the praefectus Aegypyi, Rhodon.
As patriarch, Paul's first act was to have Psoes, a Miaphysite deacon who wrote in Coptic and was a thorn in the government's side, delivered to Rhodon to be tortured to death.
The people of Alexandria revolted in fury, and to pacify them Justinian recalled Rhodon and executed him in Constantinople for his role in the martyrdom of Psoes, despite having previously send thirteen dispatches ordering Rhodon to obey Paul.