Церковь построена была военным Сергиево-Пантелеймо- новским братством хоругвеносцев в честь рождения великой

княжны Анастасии Николаевны, отсюда и ее редкое посвящение. Пока этот храм стоял на московской земле, он оставался мемориалом несчастной царевны, расстрелянной большевиками в Ипатьевском доме в 1918 году.

История храма в Старом Зыкове началась в июле 1901 года, когда член Сергиево-Паптелеймоновского братства крестьянин Андриан Рощин выразил желание увековечить день рождения царской дочери, построив на свои средства часовню на 200 человек. Командующий войсками Московского военного округа великий князь Сергей Александрович поддержал инициативу крестьянина. В ходе строительства планы братства изменились, и в Петровском парке вырос храм, вмещавший 700 молящихся.

Сергиево-Пантелеймоновское братство выстроило рядом с храмом женскую гимназию, мужское училище и начальную школу. О построении храма особую заботу проявил член братства московский купец 1 -й гильдии Алексей Судаков.

Церковь была достаточно скромным архитектурным произведением: протяженное здание с граненой апсидой, над которой был шатрик с крестом. Впоследствии церковь расширялась и достраивалась. В 1913 году в ней были устроены приделы Богоматери «Скоропослушницы» и св. Патриарха Гермогена. В 1920 году близ храма выстроили отдельно стоящую деревянную звонницу на столбах; колокола для нее, как ни странно выглядит этот факт для советских времен, пожертвовало артиллерийское ведомство.

После революции церковь сохранялась недолго. В апреле 1922 года из нее изъяли более пуда серебра. В июне 1931 года президиум Мособлисполкома припял решение закрыть церковь Анастасии под тем предлогом, что прихожан в ней немного, а здание необходимо соседней школе для «культурно- просветительной работы».

В одном из архитектурных сборников 1935 года церковь Анастасии Узорешительницы фигурирует как пример «пластических акцентов» зодчества: «Много есть чему поучиться в этом отношении в самой Москве, даже в отдаленных ее углах.