Стефано-Афанасьевский монастырь в селе Вотча был основан в XIV веке святителем Стефаном Пермским. Согласно Вычегодско-Вымской летописи, под 1384 годом святитель Стефан построил храмы «монастырские ж на Вотче и на Еренском горотке». Обитель была упразднена в XVIII веке, и исторических сведений о её раннем периоде сохранилось крайне мало.
В писцовой книге 1586 года упоминается деревянный храм в честь Рождества Пресвятой Богородицы. К концу XVIII века здание пришло в ветхость, и в 1790 году была возведена новая деревянная церковь с приделом во имя святителя Стефана Пермского. В 1829 году началось строительство двухэтажной каменной церкви на месте древнего городища Карыйил. Нижний зимний храм был освящен в 1830-х годах во имя святителей Афанасия и Кирилла Александрийских, с приделами в честь святителя Тихона Амафунтского и мучеников Флора и Лавра. Верхний летний храм освятили в 1841 году в честь Рождества Пресвятой Богородицы.
В 1876–1879 годах на средства прихожан вокруг храма возвели каменную ограду с железными решетками. В начале XX века стены второго этажа были расписаны устюжским художником Жилиным. После революции храм функционировал до начала 1930-х годов, затем был закрыт и использовался как складское помещение. С 1960-х годов здание оставалось заброшенным и постепенно разрушалось.
В 1994 году в Вотче был построен деревянный храм в честь мученика Виктора (Островидова). 17 июля 1996 года Священный Синод РПЦ принял решение о возрождении монастыря как мужского. Однако в 1999 году братия во главе с наместником перешла в юрисдикцию Русской Православной Церкви Заграницей. 6 октября 1999 года монастырь был воссоздан как женский. Каменный Богородице-Рождественский храм был передан обители в полуразрушенном состоянии. Основная деятельность монастыря сосредоточилась на подворье в поселке Первомайский, где был устроен домовой храм во имя святителя Стефана Пермского.