Първите сведения за на манастир са от житието на Света Теодора Солунска. Когато в 837 година Теодора избягала тук едва на 25-годишна възраст, за да стане монахиня, манастирът е посветен на Свети архидякон Стефан. В манастира според житието има параклис „Света Ботородица“, в който е погребана светицата, гробище, трапезария, магерница, конаци, мелница, кладенец. Вероятно е бил подобен на „Света София“, но по-малък.[1]
След пренасянето на мощите на светицата в него през август 893 година, манастирът е преименуван на нейно име. Монахиня в манастира е сестрата на солунския архиепископ от XIV век Нил Кавасила и майка на Николай Кавасила. След падането на Солун под османска власт в 1430 година, мощите на светицата са поругани, но манастирът не е превърнат в джамия и остава един от трите работещи солунски манастира, като има 200 монахини. На турски е наричан Кизлар манастир (Kizlar Manastir), тоест девически манастир. По неясни причини през XVIII век престава да бъде манастир и става енорийска църква. Църквата пострадва от пожара в 1890 година и от големия пожар в 1917 година, когато е напълно разрушена. Единствената сграда, която оцелява е камбанарията на храма, която е построена в края на XIX век.[1] По чудо от пожара оцеляват мощите на светицата, които до възстановяването на манастира са прехвърлени в „Света София“.[3]
Новата църква започва да се строи в близост до стария католикон през 1935 година и е открита на 9 май 1954 година от митрополит Пантелеймон Солунски, като мощите на Света Теодора Солунска са пренесени в новия храм.[3] В 1957 митрополит Пантелеймон открива западното крило на манастира, в което има духовно училище. От 1974 година работи като мъжки манастир, а през 1989 година в манастира е основан Център за агиографски изследвания на Солунската митрополия. Със свои средства манастирът издържа училището-интернат „Свети Антоний“ и издава книги.[1]
