Возведение церкви в деревне Бычиха Городокского района было начато весной 2010 г. Раньше в деревне церкви никогда не было. Строительство велось на средства уроженки деревни, ныне жительницы Москвы, Анастасии Петровны Оситис. На месте церкви когда-то стоял дом ее бабушки. Территориальная епархия сначала против такого местоположения возражала и предлагала построить храм в более живописном месте.
Благословение на строительство дал Митрополит Филарет. Было принято решение построить храм в стиле православного зодчества XIII-XVI веков. Работы вели минские строители. В ноябре того же года на строящуюся церковь вознесли купол, крест, а на звонницу установили десять колоколов, чин освящения совершил архиепископ Витебский и Оршанский Димитрий.
25 сентября 2011 г. Патриарший Экзарх всея Беларуси, Митрополит Минский и Слуцкий Филарет совершил освящение храма в честь святой великомученицы Анастасии Узорешительницы и Божественную литургию в новоосвященном храме.
По сообщениям сайтов ctv.by, patriarchia.ru, dvina.by, news.21.by