Premier jour de la semaine sans fête assignée : on dit la messe du premier dimanche après la Pentecôte, occulté par la fête de la Sainte Trinité.
Le martyrologe commence ainsi :
A Constantinople, l'anniversaire de saint Paul, évêque de cette ville. Plusieurs fois chassé de son siège par les ariens, à cause de la Foi Catholique, puis rétabli par le pontife romain Jules Ier, il fut enfin relégué par Constance, empereur arien, à Cucuse, petite ville de Cappadoce ; là, les manœuvres cruelles des ariens le firent étrangler et il entra ainsi au royaume des cieux. Sous l'empereur Théodose, son corps fut transféré avec les plus grands honneurs à Constantinople.
Paul fut étranglé par ses gardiens, qui utilisèrent son omophore, comme le montre cette miniature du Ménologe de Basile II (autour de l’an 1000).
Père vénérable, ayant revêtu l'ornement pontifical, tu imitas le zèle de ton homonyme, l'apôtre Paul, supportant comme lui persécutions et dangers, et tu pris la peine de mettre fin aux blasphèmes d'Arius; souffrant pour la Trinité éternelle et consubstantielle, tu renversas l'impie Macédonius, adversaire de l'Esprit; puis, ayant précisé pour tous la vraie foi, tu partageas la demeure des Anges immatériels; avec eux désormais intercède, toi aussi, pour le salut de nos âmes.
Doxastikon des vêpres byzantines.