Καταγόταν ἀπὸ τὴν πόλη Ἐλαία, ποὺ βρίσκεται κοντὰ στὴν Πέργαμο τῆς Μ. Ἀσίας. Γεννήθηκε ἀπὸ γονεῖς εὐσεβεῖς, τὸν Ἀντίοχο καὶ τὴν Εὐδοκία, οἱ ὁποῖοι νωρὶς πέθαναν καὶ ἄφησαν τὸν Παῦλο ὀρφανὸ καὶ ἀπροστάτευτο. Ἔτσι ὁ Παῦλος ἀναγκάστηκε νὰ βόσκει χοίρους γιὰ νὰ ζήσει.

Ὁ μεγαλύτερος ἀδελφός του Βασίλειος, ποὺ ἀσκήτευε στὸ ὄρος Λάτρος (Δυτικὴ Μ. Ἀσία, κοντὰ στὴν ἀρχαία Μίλητο), ἔμαθε τὴν κατάσταση τοῦ Παύλου καὶ ἔστειλε κάποιο μοναχὸ νὰ τὸν βρεῖ καὶ νὰ τὸν φέρει στὴ Μονή. Στὴν ἀρχὴ οἱ χωρικοὶ ἀρνήθηκαν νὰ δώσουν τὸν ὀρφανό, ἀλλὰ ὁ ἀδελφός του τὸν ἐμπιστεύθηκε στὸν ἀσκητὴ Πέτρο σὰν μαθητευόμενο.

Κοντὰ στὸν Πέτρο, ὁ Παῦλος διδάχτηκε τὴν μοναχικὴ ζωὴ καὶ τόσο πολὺ διακρίθηκε σ’ αὐτή, ὥστε μετὰ τὸν θάνατο τοῦ Πέτρου οἱ μοναχοὶ τὸν κάλεσαν στὴν ἡγουμενία τῆς Μονῆς. Αὐτὸς ὅμως δὲν δέχτηκε καὶ ἔφυγε πιὸ μέσα στὸ βουνὸ καὶ ζοῦσε μὲ αὐστηρὴ νηστεία καὶ προσευχή.

Ἔπειτα κατέβηκε στὰ κάτω μέρη τοῦ βουνοῦ καὶ ἔκτισε ὡραῖο ναὸ στὸ ὄνομα τῆς Ἁγίας Τριάδας, ὅπου καὶ παρέμεινε μέχρι τέλους τῆς ζωῆς του, ἀφοῦ ἔκανε καὶ πολλὰ θαύματα.
Μερικοὶ Συναξαριστὲς ἀναφέρουν ὅτι πέθανε σὲ βαθιὰ γεράματα τὸ 896.