miejscem wspomnienia poległych wojowników stała się dopiero kilkanaście lat od powstania. Drewniana świątynia była niszczona przez pożary w 1493 i 1547. Budynek miał dwa ołtarze: główny Wszystkich Świętych i boczny św. Nauma, od strony południowej. W 1612 została natomiast poważnie uszkodzona podczas walk o Moskwę.
Budynek obecnie istniejącej (2015) cerkwi datowany jest na XVI w., możliwe jednak, że murowana świątynia istniała już wcześniej, a w XVI w., przy wznoszeniu nowego obiektu, wykorzystano fragment murów poprzedniego. W I połowie XVII w. cerkiew Wszystkich Świętych była świątynią jednonawową, na planie kwadratu, z apsydą i galerią otaczającą przedsionek i nawę. W 1662 dobudowany został drugi ołtarz św. Mikołaja. Dwadzieścia sześć lat później, w ramach odbudowy obiektu po kolejnym pożarze, cerkiew poszerzono o przedsionek i dzwonnicę, rozebrano natomiast część galerii. Została ona ostatecznie zlikwidowana w 1737, podczas następnej przebudowy obiektu. Między XVII a XIX wiekiem cerkiew była wielokrotnie remontowana. Przez cały okres swojego istnienia posiadała status świątyni parafialnej.