Ο Άγιος Θεόδωρος καταγόταν από τη Μυτιλήνη. Υποκύπτοντας στον πειρασμό, απαρνήθηκε τον Χριστό και αποδέχθηκε το Ισλάμ. Συνειδητοποιώντας το λάθος του, μετανόησε και έφτασε στο Άγιον Όρος, όπου εξομολογήθηκε την αμαρτία του και εργάστηκε για την πνευματική του σωτηρία. Ωστόσο, γεμάτος αγάπη για τον Θεό, θέλησε να φτάσει ως το μαρτύριο. Ενισχυμένος από τη δύναμη της προσευχής και την ευχή του πνευματικού του πατέρα, επέστρεψε στην πατρίδα του για να ομολογήσει την πίστη του.
Στάθηκε τότε ενώπιον του δικαστή και μίλησε για την αλήθεια του χριστιανισμού, εκφράζοντας την επιθυμία να υπερασπιστεί τον αληθινό Θεό. Ο δικαστής, μη κατανοώντας τη στάση του, διέταξε να τον φυλακίσουν. Μετά από πολλές ανακρίσεις και χωρίς να καταφέρει να τον μεταπείσει, τον καταδίκασε σε θάνατο. Ο άγιος υπέστη σκληρά βασανιστήρια, κατά τη διάρκεια των οποίων παρέμεινε αμετακίνητος.
Φτάνοντας στον τόπο της εκτέλεσης, προσευχήθηκε και, ζητώντας συγχώρεση από τους χριστιανούς, ανέβηκε στην αγχόνη. Τα άγια λείψανά του ρίχτηκαν στη θάλασσα, όμως σύντομα ανασύρθηκαν και τάφηκαν από τους πιστούς στην εκκλησία του Αγίου Ιωάννη του Βαπτιστή.
Ο Άγιος Θεόδωρος μαρτύρησε το 1784.
