Bρίσκεται στην πλατεία Κλαυθμώνος. Είναι κτίσμα των μέσων του 11ου αι.και ανήκει στον τύπο του δικιόνιου ναού, αλλά σε μία ιδιαίτερη παραλλαγή: Οκταγωνικός και με δίλοβα μικρά παράθυρα τρούλος στηρίζεται ανατολικά σε δύο κίονες και δυτικά σε δύο πεσσούς, οι οποίοι είναι ενσωματωμένοι στον δυτικό τοίχο. Χαρακτηριστική είναι η επιμελημένη πλινθοπερίκλειστη τοιχοποιία της εκκλησίας, που έχει διακόσμηση με κουφικά γράμματα, φυτά, ζώα κλπ.

Στη δυτική πλευρά έχει δύο θύρες, με αψίδωμα και παραστάδες, μία στο κέντρο και μία προς βορρά, ενώ προς νότο, αντί θύρας έχει ένα μικρό μονόλοβο αψιδωτό παράθυρο. Σε ψηλότερο σημείο, επάνω από την κεντρική θύρα, έχει ένα δίλοβο αψιδωτό παράθυρο. Στη νότια πλευρά υπάρχει μια ακόμα αψιδωτή θύρα με ένα δίλοβο αψιδωτό παράθυρο, και λίγο πιο πάνω ένα πλατύ τρίλοβο μεταγενέστερο κωδωνοστάσιο.

Στην ίδια πλευρά υπάρχουν ακόμα δύο μονόλοβα παράθυρα και ένα δίλοβο. Αντίστοιχα όμοια παράθυρα υπάρχουν και στη βόρεια πλευρά, αλλά δεν έχει ανοιχθεί σ’ αυτή θύρα.
Στη θέση της σημερινής εκκλησίας υπήρχε άλλη, παλαιότερη, μια από τις δώδεκα που, σύμφωνα με την παράδοση, ανήγειρε στην ιδιαίτερη πατρίδα της η αυτοκράτειρα Ευδοκία (+ 460).

Τη σημερινή εκκλησία, προς τιμή του μάρτυρος Θεοδώρου του Τήρωνος (;) αρχικά, ανήγειρε ο σπαθαροκανδιδάτος βυζαντινός αξιωματούχος, που είχε το δικαίωμα να φορεί λευκή τήβεννο, Νικόλαος Καλόμαλος, επειδή η προηγούμενη εκκλησία ήταν μικρή και πολύ σαθρή. Σχετική είναι η ακόλουθη επιγραφή, που έχει εντοιχισθεί επάνω από τη δυτική κεντρική είσοδο και της οποίας, επειδή σε μερικά της σημεία είναι θραυσμένη, η ανάγνωση δεν είναι καθ’ όλα βέβαιη:
+ Τόν πρίν παλαιόν ὄντα σου ναόν, μάρτυς, καί μικρόν καί πήλινον καί σαθρόν λίαν, ἀνήγειρεν Νικόλαος σός οἰκέτης, ὁ Καλόμαλος, σπαθαροκανδιδᾶτος,ὅς εὔρεν σε προστάτην παιδιόθεν μέγαν, βοηθόν καί πρόμαχον πολλῶν κινδύνωνˑ ὅν καί πρέσβενε τοῦ ἄνω τυχεῖν κλήρου, λαβόντα τήν ἄφεσιν τῶν ἐσφαλμένων.
Επιγραφή σε άλλη μικρή εντοιχισμένη πλάκα, δίπλα από την προηγούμενη, αναφέρει:
+ Μηνί Σεπτεμβρίω,ἰνδικτιῶνος γ’, ἔτους ςφνη,
δηλαδή 1049, αλλ’ οι επιστήμονες δεν συμφωνούν αν υπάρχει σχέση ανάμεσα στις δύο επιγραφές.
Όσον αφορά τον κτίτορά της, έχει διασωθεί η σφραγίδα του, η οποία αναγράφει:
Νικολάου σφράγισμα τοῦ Καλόμαλου.

Μερικοί ερευνητές, με βάση επιστολή του Πάπα Ιννοκεντίου, του έτους 1208, διατυπώνουν την άποψη πως η εκκλησία ήταν Καθολικό Μονής πάντως στα πριν από την Επανάσταση χρόνια, όπως και για πολλά μετά από αυτήν, ήταν ενοριακή. Σήμερα είναι παρεκκλήσιο του Τ.Π.Ο.Ε.Κ.Ε.
Εξαιτίας των πολλών φθορών που υπέστη κατά τη διάρκεια του ιερού Αγώνα, λίγο αργότερα, το 1840, επεσκευάσθη, με συνδρομή πολλών, ανάμεσα στους οποίους ήταν και οι βασιλείς Όθων και Αμαλία, μάλιστα επί σειράν ετών, στις 8 Σεπτεμβρίου κάθε έτους, τελούνταν «η επέτειος εορτή». Το 1910, κατά την πλακόστρωση του Ναού, διαπιστώθηκε κάτω από το δάπεδο η ύπαρξη τάφων. Επίσης στα έργα συντήρησης του Ναού το 1967, βρέθηκαν από την Αρχαιολογική Υπηρεσία άλλοι δεκαέξι τάφοι και τμήμα μωσαϊκού δαπέδου ρωμαϊκής εποχής.
Η εκκλησία των Αγίων Θεοδώρων έχει χαρακτηρισθεί από ειδικούς ως το καλύτερο βυζαντινό μνημείο της πόλης