Ciężka zima na przełomie lat 1949/1950 ukazała na niezbędność istnienia ogrzewanych pomieszczeń mieszkalnych, jak również cerkwi, która pozwalałaby uczestniczyć w kilkugodzinnych nabożeństwach także w obliczu kilkunastostopniowego mrozu (główna cerkiew Przemienienia Pańskiego była świątynią zupełnie nieogrzewaną). W związku z tym w 1950 na południowym krańcu monasterskiego wzgórza rozpoczęto budowę nowej cerkwi, tak zwanej „zimowej”. Budowany budynek miał pomieścić zarówno ogrzewaną piecem kaflowym świątynię, jak i przylegające do niej cele dla najstarszych sióstr.
Fundamenty pod cerkiew Ikony Matki Bożej „Wszystkich Strapionych Radość” poświęcił metropolita Makary – nowo wybrany zwierzchnik Polskiego Autokefalicznego Kościoła Prawosławnego. Poświęcenia ukończonej świątyni dokonano zaś 6 listopada 1956. Budynek o kształcie wydłużonego prostokąta z dwuspadowym dachem mieścił od wschodu świątynię, do której od zachodu przylegał dwukondygnacyjny budynek mieszkalny. Od strony północnej przedsionek prowadził do świątyni, a od zachodniej – do części mieszkalnej dla sióstr.
W 1963 w świątyni przeprowadzono remont (odmalowano wnętrze, poprawiono piece, rozszerzono klirosy), a w 1964 nad wejściem do niej wykonano dzwonnicę, w której zawieszono dzwon, będący darem wiernych parafii św. Jana Teologa w Chełmie.