Ο ναός των αγίων Θεοδώρων Μυτιλήνης αποτελεί τρίκλιτη βασιλική και βρίσκεται σε μικρή απόσταση από το μητροπολιτικό ναό. Σύμφωνα με την παράδοση θεωρείται ως η πρώτη μητρόπολη της Μυτιλήνης μέχρι την οθωμανική κατάληψη της πόλης και καταστράφηκε στα τέλη του 18ου αιώνος από πυρκαγιά.
Μια πρώτη ματιά στο ναό καταδεικνύει την αρχαιότητα του χώρου, αφού οι επιβλητικοί κίονες και το δομικό υλικό που έχουν χρησιμοποιηθεί μαρτυρούν στοιχεία αρχαίου δημοσίου κτιρίου. Στο εσωτερικό του ναού διακρίνεται κιονόκρανο σε δεύτερη χρήση στη βάση ενός από τους κίονες που χωρίζουν το μεσαίο από το βόρειο κλίτος.
Η ανοικοδόμηση του ναού έγινε το 1795 και έφτασε έτσι στη σημερινή μορφή. Ο ναός αγιογραφήθηκε το 1799 και το 1918 πραγματοποιήθηκαν εργασίες ανακαινίσεως, κατά τις οποίες πολλές παλιές αγιογραφίες επικαλύφθηκαν με νεότερες. Στο νότιο τοίχο σώζεται σπάραγμα από τοιχογραφία του παλιού ναού.
Το ξυλόγλυπτο τέμπλο είναι ένα απ’ τα αξιολογότερα του νησιού τα θωράκια του οποίου κοσμούνται με ανάγλυφες παραστάσεις απ’ τη Παλαιά και την Καινή διαθήκη. Αποτελεί έργο του 1812 και κατασκευάστηκε «υπό του μάστορα Σταύρου του Γιεώργη Πολιτου Χιοτη», σύμφωνα με συμφωνητικό έγγραφο.
Της αυτής τεχνοτροπίας είναι κι η αγία Τράπεζα και το κιβώριό της, έργα του 1818, όπως επίσης και ο αρχιερατικός θρόνος που έχει φιλοτεχνηθεί το 1872. Στο ναό σώζονται αξιολογότατες φορητές εικόνες, παλιότερες του 1795, γεγονός που μαρτυρεί πως προέρχονται απ’ τον παλιό ναό. Ανάμεσά τους διακρίνεται η «Παναγιά η Αγιοθεοδωρίτισσα», βυζαντινή εικόνα η οποία όπως αναφέρεται λιτανευόταν πανδήμως σ’ όλη την Μυτιλήνη.
Ο ναός εορτάζει το πρώτο Σάββατο της σαρακοστής, στις 25 Μαρτίου και στις 15 Αυγούστου.
