Сначала это была домовая вмц. Анастасии Узорешительницы в Исправительной колонии №1 на ул. Кальварийская в г. Минске. Впервые православный священник появился в исправительно-трудовых учреждениях Республики Беларусь как духовный пастырь и помощник отбывающих наказание людей в декабре 1988 г. Этим учреждением была именно Минская исправительная колония №1 по ул. Кальварийской. Пастырем был нынешний настоятель Прихода "Всех скорбящих Радость", в то время священник Минского кафедрального собора Игорь Коростелёв. До этого времени только в экстренных случаях священнику было дозволено посещать места лишения свободы после получения специального разрешения.
Первоначально духовные беседы заканчивались молебнами, затем появились желающие креститься, а в начале 1992 года начали совершаться Божественные литургии. С огромным желанием и благоговением заключённые исповедовались и причащались. Благолепие православной службы, чудесное пение церковного хора привлекали всё большее и большее количество осуждённых. В 1993 году в колонии прошло первое после 1917 г. венчание в тюрьме.
В 1997 и 2006 годах в престольный праздник домовой церкви прихода вмц. Анастасии Узорешительницы (4 января) Божественную литургию совершал митрополит Минский и Слуцкий Филарет.
Домовая вмц. Анастасии Узорешительницы в Исправительной колонии №1 на ул. Кальварийская в г. Минске просуществовала более 25 лет, но затем была снесена в связи с изменениями архитектурного плана города. На этом месте сейчас находится жилой комплекс Каскад.
В ноябре 2016 года инициативная группа жителей Минска обратилась в Минское Епархиальное управление с просьбой об образовании прихода и строительстве храма в честь Великомученицы Анастасии Узорешительницы. Община Святой Великомученицы Анастасии Узорешительницы уже сейчас ведет активную социальную и просветительскую деятельность. Существует "Школа Благочестия", проводятся молебны, лекции, концерты, благотворительные акции.