Первоначальная идея строительства храма на территории колонии принадлежит епископу Магаданскому и Синегорскому Феофану (Ашуркову). Первый молебен на месте будущего храма в начале двухтысячных годов был совершен епископом Магаданским и Синегорским Гурием (Шалимовым). Епископ Гурий принял решении о наименовании церкви в честь великомученицы Анастасии Узорешительницы.
Летом 2004 года в ИК-4 были доставлены мощи святых преподобномучениц Великой княгини Елисаветы и инокини Варвары. Ковчег с мощами был установлен на месте, где спустя 10 лет началось возведение первой тюремной церкви Колымы. Перед мощами был совершен молебен преподобномученицам в присутствии большого количества осужденных.
17 апреля 2013 года состоялась встреча епископа Магаданского и Синегорского Иоанна (Павлихина) и начальника УФСИН по Магаданской области Геннадия Викторовича Кирюшина. В ходе встречи была достигнута договоренность о начале строительства храма в ИК-4.
15 мая 2013 года епископ Магаданский и Синегорский Иоанн освятил закладной камень будущего храма.
Август 2013 года — начало строительных работ. Предполагалось построить каменный храм, автором проекта которого стал магаданский архитектор Владимир Григорьевич Колосов. Был вырыт котлован под каменный храм, который в скором времени из-за проливных дождей оказался заполнен водой. В центре колонии возникло рукотворное озеро, и от идеи каменного храма пришлось отказаться. Принято решение строить деревянный храм на основании имеющегося в наличии дореволюционного эскиза.
Сентябрь 2014 года — укреплено место строительства и установлен ленточный фундамент, основой которого стал мощный железный каркас. Брус для стен церкви выделен и передан Магаданской и Синегорской епархией по благословению правящего архиерея, епископа Иоанна (Павлихина).
Ноябрь 2014 года — стены храма возведены.
Июль-август 2015 года — ООО «Реставрационная компания «Эра» (г.Раменское Московской области) изготовила купол и крест.
15 октября 2015 года — в ИК-4 состоялось освящение креста и купола. Чин освящения совершил священник Кирилл Агеенко, окормляющий православных верующих колонии. В храме проведено первое богослужение — молебен великомученице Анастасии Узорешительнице.
10 ноября 2015 года — купол и крест установлены на здании церкви.
Декабрь 2016 года — окончание строительных работ и открытие храма для посещения осужденными.
Август 2017 года — иконы для иконостаса тюремного храма заказаны в ХПП «Софрино».
Сентябрь 2017 года — иконы доставлены в Магадан и переданы в колонию.
Апрель 2018 года — закончены изготовление резных элементов иконостаса и его установка.
https://magadan-eparchy.ru/objects/item-47.html
1 февраля 2024