Καταγόταν από τα Μύρα της Λυκίας και έζησε την εποχή του αυτοκράτορα Δεκίου. Ήταν βοσκός στο επάγγελμα.

Την εποχή εκείνη ο Ασκληπιός, ο διοικητής της Λυκίας, ξεκίνησε διωγμό κατά των χριστιανών και ο στόχος του ήταν να συλλάβει τον άγιο μάρτυρα Διοσκουρίδη. Ο Διοσκουρίδης όμως κατέφυγε στο όρος όπου έβοσκε ο Θεμιστοκλής τα πρόβατά του. Οι άνθρωποι του διοικητή κίνησαν και αυτοί προς το όρος όπου και συνάντησαν τον Θεμιστοκλή. Όταν ερωτήθηκε για την πίστη του δεν δίστασε ούτε στιγμή να ομολογήσει τον έναν και μοναδικό Θεό. Οι στρατιώτες ακούγοντας την ομολογία αυτή της πίστης του τον συνέλαβαν και τον οδήγησαν στον Ασκληπιό. Παρ' όλες τις απειλές που δέχθηκε ο άγιος έμεινε ακλόνητος στην πίστη του. Αυτό εξόργισε τον Ασκληπιό και διέταξε τον βασανισμό του.

Ο άγιος Θεμιστοκλής παρέδωσε το πνεύμα του κατά την διάρκεια του μαρτυρίου το 251 μ.Χ.

Τὰς ἐκ σιδηρῶν ὀξέων ἥλων ξέσεις, Ὥς τις σιδηροῦς καρτερεῖς Θεμιστόκλεις.