ΠΑΥΛΟΣ ὁ Ὅσιος καὶ Ὁμολογητὴς Πατὴρ ἡμῶν ἦτο ἀπὸ τὴν Κρήτην εἰς τὴν ὁποίαν ἤκμασε κατὰ τοὺς χρόνους τοῦ δυσσεβοῦς καὶ εἰκονομάχου βασιλέως Κωνσταντίνου Ε’ τοῦ Κοπρωνύμου (741-775). Ὅτε δὲ ὁ ἐναγὴς οὗτος ἐξαπέλυσε τὸν κατὰ τῶν σεπτῶν καὶ ἁγίων Εἰκόνων διωγμόν, συλληφθεὶς ὁ μακάριος Παῦλος ὑπὸ τοῦ στρατηγοῦ τῆς Κρήτης Θεοφάνους τοῦ Λαρδατύρη προσήχθη πρὸς ἐξέτασιν καὶ ἐβιάζετο νὰ καταπατήσῃ τὴν ἁγίαν Εἰκόνα τοῦ Ἐσταυρωμένου.
Δεικνύων δὲ ὁ μιαρὸς ἐκεῖνος στρατηγὸς τὴν ἁγίαν Εἰκόνα καὶ βασανιστήριον τι ὄργανον, καταπέλτην καλούμενον, λέγει πρὸς τὸν Ἅγιον· «Ἓν ἀπὸ τὰ δύο ταῦτα ποίησον, ἢ τὴν Εἰκόνα νὰ πατήσῃς διὰ νὰ ζήσῃς, ἢ θὰ σὲ βάλω εἰς ταύτην τὴν βάσανον». Ἐνδυναμωθεὶς τότε ὑπὸ τῆς Χάριτος τοῖ Παναγίου Πνεύματος ὁ μακάριος Παῦλος ἀπεκρίθη· «Μὴ γένοιτο, Κύριε Ἰησοῦ Χριστέ, νὰ πατήσω τὴν Εἰκόνα Σου», ὁμοῦ δὲ μὲ τὸν λόγον γονυπετήσας εἰς τὴν γῆν ἔκυψε καὶ ἠσπάσθη τὴν ἁγίαν Εἰκόνα.
Τούτου ἕνεκα ἐδέθη κατὰ διαταγὴν τοῦ στρατηγοῦ ὁ Ἅγιος εἰς τὸν καταπέλτην μὲ δύο σανίδας δυνατάς, εἶτα τοῦ ἐπέρασαν σίδηρα εἰς ὅλον τὸ σῶμα καὶ κατόπιν, κρεμάσαντες αὐτὸν κατωκέφαλα, ἔθεσαν πῦρ καὶ τὸν κατέκαυσαν. Οὕτως ἀπέλαβεν ὁ μακάριος τοῦ Μαρτυρίου τὸν στέφανον.