Γεννήθηκε στη Λαμπαδού ένα χωριό κοντά στο σημερινό Μιτσερό της Κύπρου, κι ήταν γιος ειδωλολάτρη ιερέα του Ιεροκλέα. Ο ιερέας διακρινόταν για τα φιλόξενα αισθήματα του και γι' αυτό δεν δίστασε να φιλοξενήσει τον Παύλο, τον Βαρνάβα και τον Μάρκο, όταν αυτοί βρέθηκαν στην Κύπρο. Τότε είλκυσαν στον Χριστό τον γιο του Ηρακλείδη και αυτός στη συνέχεια έφερε στον Χριστό τους γονείς του. Τον Ηρακλείδη ο Παύλος διόρισε επίσκοπο Ταμασίων της Κύπρου. Εργάστηκε με πολύ ζήλο, έχοντας συνεργάτη του τον Μύρωνα. Μπόρεσαν και οι δύο να φέρουν κοντά στον Χριστό πολλούς ειδωλολάτρες. Οι επιτυχίες τους όμως αυτές, προκάλεσαν τη μανία των απίστων. Και έτσι κάποια μέρα, όρμησαν οπλισμένοι επάνω τους και αφού τους θανάτωσαν, στη συνέχεια τους έριξαν στη φωτιά. Και έτσι έλαβαν το αμαράντινο στεφάνι του μαρτυρίου.

Ποίημα τοῦ Ἄρχιεπισκόπου Κύπρου κ.κ. Χρυσοστόμου. Μέγαν εὔρατο τῶν Ταμασέων, πόλις κήρυκα καὶ ποιμενάρχην, τῆς ἐκκλησίας Χριστοῦ καὶ διδάσκαλον. Τῶν γὰρ εἰδώλων τὴν πλάνην κατήργησας, φῶς ἀληθείας κηρύξας τοὶς ἔθνεσιν. Ὅθεν, ἅγιε ἱεράρχα Ἠρακλείδιε, Χριστὸν τὸν Θεὸν Ἱκέτευε, δωρήσασθαι ἠμὶν τὸ μέγα ἔλεος.