Paul apparaît dans les sources vers 717, au moment de la prise du pouvoir par Léon III l'Isaurien. Théophane le Confesseur en fait le chartulaire privé de l'empereur tandis que le patriarche Nicéphore Ier de Constantinople le décrit comme un confident loyal du souverain. Il disposerait aussi d'une certaine expérience militaire[1]. Au même moment, le stratège de Sicile Serge se révolte, pensant que Constantinople a été prise par les Arabes. Il positionne comme candidat au poste d'empereur un certain Basile Onomagoulos. Léon III réagit en nommant Paul comme nouveau stratège, avec la mission de réprimer ce soulèvement. Il pourrait alors avoir été élevé à la dignité de patrice, sauf à ce qu'il la détienne déjà[2].
Il est généralement reconnu qu'il s'agit du même homme qui devient exarque de Ravenne vers 723. Il aurait donc assumé la charge de stratège de Sicile jusqu'à cette date, même si rien ne l'atteste explicitement. Dans cette hypothèse, il aurait repoussé une attaque arabe vers 720 ou 721[3].
Quand il devient exarque, il doit lutter contre le royaume des Lombards mais fait aussi face à une opposition interne latente, alimentée par le pape Grégoire II, mécontent des réformes fiscales de l'empereur. Selon le Liber Pontificalis, Paul aurait reçu l'ordre de faire tuer le pape ou au moins de l'emprisonner. Dans tous les cas, Paul échoue dans cette tâche et est confronté à une forte opposition, tout en subissant l'anathème. Vers 726-727, la ville de Ravenne rentre en rébellion contre l'autorité impériale et les représentants de Constantinople sont renversés. Paul tente de rallier des troupes loyales à l'empereur mais il est tué. Les opposants vont jusqu'à nommer un nouvel empereur mais le pape finit par jouer les médiateurs pour mettre un terme à cette rébellion[4].
Roberto Cessi a fait l'hypothèse que le premier doge de Venise mentionné par Jean le Diacre, Paolo Lucio Anafesto, serait le même personnage que l'exarque Paul. Toutefois, l'existence de ce premier doge reste sujette à caution. De même, le deuxième doge, Marcello Tegalliano, qui serait un subordonné de Paul, pourrait aussi avoir été inventé. D'autres historiens estiment que le premier doge serait plutôt d'origine lombarde, en l'occurrence le duc de Trévise[5].
