But he is best known as a Byzantine epigrammatist who is noted for his famous hymn of praise of the Hagia Sophia, in which he described the church as if it were a meadow of marble (due to the many colours of marble employed in its construction). Through this eulogy and elaborate praise in verses of the architectural and decorative characteristics of the Hagia Sophia after the reconstruction of the dome in 562, we are able to imagine the magnificence of this basilica before it was plundered many times in the course of history. These poems were most probably commissioned by the emperor Justinian I himself. Paul had to read these verses to the emperor through the inauguration of the basilica. It consists of 1029 verses, starting with 134 iambic trimeters and the rest dactylic hexameters.
A hundred of his epigrams, a few erotic, are preserved in the Greek Anthology. These pagan epigrams are interesting primarily because of their social and historical information.
He was a close friend of Agathias Scholastikos, another author of epigrams, who provides some scarce data about his life.