Ὁ Ἅγιος Νεομάρτυς Παῦλος καταγόταν ἀπὸ τὴ Ρωσία. Αἰχμαλωτίσθηκε σὲ παιδικὴ ἡλικία ἀπὸ τοὺς Τάταρους, ἀπὸ τοὺς ὁποίους τὸν ἀγόρασε κάποιος Χριστιανὸς τῆς Κωνσταντινουπόλεως καὶ τὸν ἄφησε ἐλεύθερο. Στὴ Βασιλεύουσα ὁ Ἅγιος νυμφεύθηκε Ρωσίδα γυναίκα, ποὺ ἦταν πρῶτα αἰχμάλωτη, μετὰ τῆς ὁποίας ζοῦσε βίο εὐσεβὴ καὶ φιλόθεο.

Ὅμως ὁ Ἅγιος, ποὺ ἔπασχε ἀπὸ τὴ νόσο τῆς ἐπιληψίας, κάποια στιγμὴ σὲ ὥρα κρίσεως, ἐνῷ οἱ γείτονές του τὸν ὁδηγοῦσαν στὸ ναὸ τῆς Θεομήτορος τῆς ἐπιλεγομένης τοῦ Μογλουνίου, ὅταν συνάντησε στὸν δρόμο κάποιους Τούρκους, ἄρχισε νὰ ζητᾶ βοήθεια ἀπὸ αὐτοὺς καὶ νὰ φωνάζει «Εἶμαι Ἀγαρηνός».
Οἱ Τοῦρκοι ἀνέφεραν τὰ συμβάντα στὸν βεζίρη, ὁ ὁποῖος διέταξε τὴν σύλληψη τοῦ Ἁγίου Παύλου καὶ τὸν ἱερέων τοῦ ναοῦ. Ὅταν ὁ Ἅγιος συνῆλθε ἀπὸ τὴν κρίση τῆς ἀσθένειάς του, ὁδηγήθηκε ἐνώπιον τοῦ ἄρχοντος, ὁ ὁποῖος τοῦ ζήτησε νὰ ὁμολογήσει ἐπίσημα τὸ Μουσουλμανισμό, ὑποσχόμενος πλοῦτο καὶ τιμὲς καὶ ἀπειλώντας μὲ βασανιστήρια καὶ θάνατο. Ὁ Παῦλος, ἐνδυναμούμενος καὶ ἀπὸ τὴν σύζυγό του, ὁμολόγησε μὲ παρρησία τὸ Ὄνομα τοῦ Χριστοῦ. Ἔτσι τὸν ἔριξαν στὴ φυλακὴ καὶ τὸν βασάνισαν. Ἀφοῦ κήρυξε καὶ πάλι τὴν πίστη του στὸν Χριστὸ μπροστὰ στὸ βεζίρη, τὴ Μεγάλη Παρασκευὴ τοῦ ἔτους 1683, ὁδηγήθηκε δέσμιος στὸν ἱππόδρομο Ἀτμεϊντάν, ὅπου τοῦ ἀπέκοψαν τὴν τίμια κεφαλή του.