Ο Όσιος Παύλος καταγόταν από την πόλη Ελαία, που βρίσκεται κοντά στην Πέργαμο της Μικράς Ασίας. Γεννήθηκε από γονείς ευσεβείς, τον Αντίοχο και την Ευδοκία, οι οποίοι νωρίς πέθαναν και άφησαν τον Παύλο ορφανό και απροστάτευτο.
Έτσι ο Παύλος αναγκάστηκε να βόσκει χοίρους για να ζήσει.
Ο μεγαλύτερος αδελφός του Βασίλειος, που ασκήτευε στο όρος Λάτρος (Δυτική Μικρά Ασία, κοντά στην αρχαία Μίλητο), έμαθε την κατάσταση του Παύλου και έστειλε κάποιο μοναχό να τον βρει και να τον φέρει στη Μονή.
Στην αρχή οι χωρικοί αρνήθηκαν να δώσουν τον ορφανό, αλλά ο αδελφός του τον εμπιστεύθηκε στον ασκητή Πέτρο σαν μαθητευόμενο.
Κοντά στον Πέτρο, ο Παύλος διδάχτηκε τη μοναχική ζωή και τόσο πολύ διακρίθηκε σ’ αυτή, ώστε μετά τον θάνατο του Πέτρου οι μοναχοί τον κάλεσαν στην ηγουμενία της Μονής. Αυτός όμως δεν δέχτηκε και έφυγε πιο μέσα στο βουνό και ζούσε με αυστηρή νηστεία και προσευχή.
Έπειτα κατέβηκε στα κάτω μέρη του βουνού και έκτισε ωραίο ναό στο όνομα της Αγίας Τριάδας, όπου και παρέμεινε μέχρι τέλους της ζωής του, αφού έκανε και πολλά θαύματα.
Μερικοί Συναξαριστές αναφέρουν ότι πέθανε σε βαθιά γεράματα το 896 μ.Χ.
