Według podań, wojewoda ruski Roman (lub książę Roman Ostrogski, brat króla Daniela Halickiego, według wersji Jabłonowskiego) został otoczony przez wojska chana Buniaka. We śnie ukazał mu się św. Mikołaj, który nakazał mu stoczyć bitwę i w miejscu przyszłego zwycięstwa zbudować cerkiew ku czci Najświętszej Bogurodzicy, a między trzema wałami, gdzie odpoczywał, – cerkiew ku czci samego św. Mikołaja. Odniósłszy zwycięstwo nad Tatarami, Roman wypełnił te wskazówki, fundując klasztor św. Mikołaja w Zawałowie. Wspólnota została zniszczona podczas najazdów turecko-tatarskich w połowie XVII wieku, w szczególności w 1675 roku przez wojska Kara Mustafy.
Odrodzenie i gospodarka Odrodzenie klasztoru rozpoczęło się pod koniec XVII wieku, a od 1700 roku jego głównym budowniczym został igumen Sylwester Tarasewicz, który odbudował drewnianą trójkopułową cerkiew i nowe cele. Otrzymał on przywileje na ziemie i młyn od dziedzica Aleksandra Jana Jabłonowskiego w 1714 i 1721 roku, co zapewniło wspólnocie niezależność ekonomiczną.