Ο Άγιος Οσιομάρτυρας Παύλος καταγόταν από την Κρήτη και μαρτύρησε επί του αρχισατράπου της νήσου Κρήτης, Θεοφάνους Λαρδοτύρου, όπως πληροφορούμαστε από τον βίο του Αγίου Στεφάνου του Νέου, του οποίου την μνήμη τιμά η Εκκλησία στις 28 Νοεμβρίου.Ο Στέφανος ήταν μοναχός στο όρος Αυξεντίου της Βιθυνίας, συνελήφθη ως εικονόφιλος και φυλακίσθηκε στην Κωνσταντινούπολη επί αυτοκράτορα Κωνσταντίνου Ε' του Κοπρώνυμου (740 - 775 μ.Χ.). Μέσα στην φυλακή βρήκε και άλλους 342 μοναχούς, που είχαν φυλακισθεί για τον ίδιο λόγο, μεταξύ των οποίων και έναν μοναχό από την Κρήτη με το όνομα Αντώνιος. Αυτός άρχισε να διηγείται στους άλλους φυλακισμένους μοναχούς περί της αγριότητας των διωγμών στην Κρήτη και περί του μαρτυρίου του Αγίου Παύλου.
Ο αρχισατράπης Θεοφάνης, αφού οδήγησε τον Άγιο Παύλο στο Πραιτώριο του Ηρακλείου, τον εκβίαζε ή να ποδοπατήσει την εικόνα του Κυρίου, ο Οποίος σταυρώθηκε για τον άνθρωπο, ή να ακολουθήσει την οδό των βασανιστηρίων. Ο Άγιος όχι μόνο αρνήθηκε να το πράξει, αλλά γονάτισε και ασπάσθηκε την εικόνα. Εξαγριωμένος ο αρχισατράπης έδωσε εντολή να γδύσουν τον Άγιο και να τον δέσουν με σίδερα. Κατόπιν, αφού τον κρέμασε, τον έκαψε ζωντανό. Το μαρτύριό του τοποθετείται περί το 765 ή το 766 μ.Χ.
