Η ύπαρξη της μονής του αγίου Στεφάνου στη Θεσσαλονίκη γίνεται γνωστή σ’ εμάς από τον βίο της αγίας Θεοδώρας. Λόγω της η οποία μόνασε εκεί, αγίασε και ανέδειξε μετά την κοίμησή της την Μονή σε σπουδαίο ιερό Προσκυνηματικό χώρο εξαιτίας των πολλών θαυμάτων της, καθιερώθηκε ως μονή της Αγίας Θεοδώρας.
Η αγία προσέφυγε στη μονή του αγίου Στεφάνου σε ηλικία 25 ετών και έγινε μοναχή προσφέροντας συγχρόνως ολόκληρη την περιουσία της στην μονή.
Το πόσο σημαντική είναι η μονή αποδεικνύεται και από το γεγονός οτι σε αυτή μόνασαν η αδελφή του Aρχιεπισκόπου Θεσσαλονίκης αγίου Νείλου Καβάσιλα και η μητέρα του αγίου Νικολάου Καβάσιλα του Χαμαετού.
Μία άλλη πληροφορία για την ιστορική πορεία της μονής προέρχεται από το “Οδοιπορικό” του Ρώσσου Ιγνατίου του εκ Σμολένσκ κατά την επίσκεψή του στην Θεσσαλονίκη και το Άγιον Όρος το 1405. Το κείμενο του οδοιπορικού έχει ως εξής:
“Ἐν ἔτει 1405 Ἰγνάτιος ὁ Σμολνιάνιν εὑρέθη ἐν Θεσσαλονίκῃ καί προσεκύνησε τόν ἅγιον Δημήτριον καί τήν ἁγίαν Θεοδώραν τήν μυροβλύτιδα καί ἔλαβεν ἐκ τοῦ ἁγίου Μύρου αὐτῶν…”
Λίγο αργότερα επισκέφθηκε την μονή και ο Ρώσσος διάκονος Ζωσιμάς, ο οποίος έμεινε έκπληκτος από την θέα του λειψάνου της αγίας, γιατί φαινόταν σαν να ζούσε και προσθέτει ότι τα ενδύματα του λειψάνου ήταν διαποτισμένα από το μυρίπνοο έλαιο που πήγαζε απ’ αυτό.
Το 1430 με την άλωση της Θεσσαλονίκης, οι Τούρκοι κατατεμάχισαν το άγιο λείψανο. Ωστόσο η μονή της αγίας Θεοδώρας δεν δημεύθηκε, ούτε ακολούθησε την τύχη πολλών μονών και ναών της πόλης, οι οποίες αφού δημεύθηκαν από τον Μουράτ Β’, μετατράπηκαν σε τζαμιά. Μάλιστα κατ’ αυτήν την περίοδο μνημονεύεται από πολλούς ξένους περιηγητές, διότι ήταν μία από τις τρεις μονές που λειτουργούσαν στη Θεσσαλονίκη μετά την άλωσή της, καθώς, σύμφωνα με όσα αναφέρει ο άγιος Φιλόθεος ο Κόκκινος, η μονή βρισκόταν υπό την προστασία της Μάρας Μπράνκοβιτς, μητριάς του Μωάμεθ Β΄του Πορθητή, η οποία είχε αγοράσει τη μονή κατά το έτος 1459. Την ίδια περίοδο σημειώνει ο Θεσσαλονικέας ιερέας Ιωάννης Θολοΐτης πως η γυναικεία ιερά μονή της αγίας Θεοδώρας αριθμούσε διακόσιες (200) μοναχές, γεγονός το οποίο μαρτυρεί μία σημαντική άνθηση της μονής. Άλλες πληροφορίες για την μονή και την γύρω συνοικία της αντλούμε από τα φορολογικά κατάστιχα που καταρτίστηκαν το 1906.
Η μονή ονομαζόταν τουρκικά Kizlar Manastir (Μοναστήρι των Κοριτσιών), αν και η τουρκική της ονομασία δεν επικράτησε μεταξύ των χριστιανικών πληθυσμών, οι οποίοι εξακολουθούσαν να την αποκαλούν με το αρχικό της όνομα. Η συνοικία της αποτελούσε μία από τις δώδεκα χριστιανικές συνοικίες της πόλης. Εκτός των άλλων περιελάμβανε ένα σπίτι για τους ιερείς της, ένα σχολείο και ένα κατάστημα που ανήκαν στην μονή, όπως επίσης και ένα παρεκκλήσι στην συνοικία του αγίου Κωνσταντίνου στην πλατεία Ιπποδρομίου.
Το καθολικό της μονής επλήγη καίρια κατά τις δύο πυρκαγιές του 1890 και 1917. Η πυρκαγιά του 1917 κατέστρεψε ολοκληρωτικά το καθολικό της μονής. Το μόνο κτίσμα που διασώθηκε ήταν το κωδωνοστάσιο του ναού, το οποίο κτίστηκε στα τέλη του 19ου αιώνος.
Ο νέος ναός κτίστηκε πλησίον του κατεστραμμένου καθολικού το 1935. Το 1957 ο Μητροπολίτης Θεσσαλονίκης Παντελεήμων ο Α’ (Παπαγεωργίου) ανήγειρε την δυτική πτέρυγα της μονής, όπου λειτούργησαν διαδοχικά φοιτητικό οικοτροφείο και Εκκλησιαστική σχολή.
Το 1974 ο Μητροπολίτης Παντελεήμων ο Β’ (Χρυσοφάκης) ανασυγκρότησε και περάτωσε τα έργα στην μονή της Αγίας Θεοδώρας, η οποία έκτοτε λειτουργεί ως ανδρώα και αριθμεί 54 πατέρες, αγάμους κληρικούς της Ιεράς Μητροπόλεως Θεσσαλονίκης. Στη μονή φιλοξενούνται επίσης εκκλησιαστικές αποστολές και αγιορείτες πατέρες και διαμένουν ξένοι ιερείς-φοιτητές του Πανεπιστημίου.
Από το 1981 ιδρύεται στο χώρο της μονής το Κέντρο Αγιολογικών Μελετών της Ιεράς Μητροπόλεως Θεσσαλονίκης. Η μονή συντηρεί με δικούς της πόρους το οικοτροφείο αρρένων «Ο άγιος Αντώνιος» και προβαίνει σε εκδόσεις βιβλίων.