Монастырь основан происходившим из Подмосковья учеником и родственником преподобного Сергия Радонежского — преподобным Никитой, бывшим настоятелем Высоцкого монастыря в Серпухове, а затем Высоко-Покровского монастыря в Боровске. Первоначально все постройки обители были деревянными. В XVI веке деревянные стены монастыря защищали Кострому на подступах к городу. В 1559 году началось строительство Богоявленского собора — самого древнего из сохранившихся в городе Костроме каменных сооружений. Инициатором его строительства был игумен Исайя, а одним из наиболее крупных жертвователей являлся князь Владимир Андреевич Старицкий, двоюродный брат царя Ивана Грозного.
В XVI веке к обители были приписаны два женских монастыря — Анастасиин и Крестовоздвиженский. В 1569 году монастырь посетил князь Владимир Андреевич Старицкий, направлявшийся с войском для защиты Астрахани, братия во главе с игуменом с честью встретила его, что послужило, вместе с торжественным приёмом, оказанным князю жителями Костромы, поводом для окружения царя Ивана Грозного оговорить перед ним князя. В конце того же года князя Владимира убили по приказу царя в Александровской слободе. Царский гнев обрушился и на богоявленских иноков, значительная их часть вместе с игуменом Исайей была также казнена в 1570 году.
Монастырь пострадал в Смутное время. В конце 1608 года отряды Лжедмитрия II во главе с А. Лисовским осадили Богоявленскую обитель. Несмотря на оборону монастыря, которую вели монахи и монастырские крестьяне, 30 декабря польские отряды ворвались в монастырь, разграбили его и разгромили. При этом погибли 11 иноков: три иеромонаха — Трифилий, Макарий и Савватий, иеродиакон Афиноген, иноки — Варлаам, Дионисий, Иов, Кирилл, Максим, Иоасаф и Гурий, 5 монастырских служебников, Василий, Иван, Стефан, Никита и Диомид, и 38 монастырских крестьян.
В 1918 году монастырь был закрыт, однако Богоявленский собор стал приходским храмом и действовал до 1924 года. С 1925 года в здании закрытого собора размещалось губернское архивное бюро, ставшее затем областным архивом. В 1920—1930 годах были почти полностью уничтожены монастырские стены и большинство башен, разрушены Никольский храм и Никольская часовня. В 1982 году в Богоявленском соборе, используемом как хранилище областного архива произошел пожар, уничтоживший остатки фресок собора XVII века.
Монастырь был возрожден как Богоявленско-Анастасиин женский определением Священного Синода Русской православной церкви 20 июля 1990 года. В марте 1991 года из Успенского Пюхтицкого монастыря прибыли первые насельницы. 17 августа 1991 года Богоявленский собор стал кафедральным собором Костромской епархии Русской православной церкви. Сюда перенесли главную святыню Костромы — Феодоровскую икону Божией Матери. В 1991 году начались богослужения в Смоленской церкви. В 2006 году был восстановлен храм во имя преподобного Сергия Радонежского и преподобного Никиты Костромского в подклете собора. В 1993—1997 годах были расселены западный и больничный корпус, а в 2001 году — восточный корпус, которые использовались как жилые здания. При участии администрации города Костромы была полностью восстановлена монастырская стена по улице Симановского. Возродилось монастырское кладбище, а на месте разрушенного Никольского храма воздвигнут памятный крест. При монастыре созданы две гостиницы для посещающих обитель паломников и священнослужителей.
В 2002 году на территории монастыря был установлен памятник св. влкм. Феодору Стратилату, освященный в день празднования Феодоровской иконы Божией Матери Святейшим Патриархом Московским и всея Руси Алексием II.
В настоящее время на территории Богоявленско-Анастасииного женского монастыря располагаются Костромское епархиальное управление и Костромская духовная семинария. Проход посетителей на территорию монастыря запрещён, открыты только наружные входы Богоявленского собора и часовни.
При монастыре действуют приют для девочек-сирот во имя св. Иоанна Кронштадтского и богадельня для престарелых во имя святой Марии Магдалины.
