Считается, что древняя часовня с Владимирским образом была выстроена здесь, на подступах к Кремлю, в том же 1395 г., когда икону встречали в Москве, или же позднее, но именно в честь этого события, по московскому обычаю. Та к или иначе, часовня стояла тут задолго до построения стены Китай-города. И когда в 1534 г. итальянский зодчий Петрок Малый, архитектор кремлевской Успенской звонницы, стал возводить крепостную стену, то на этом участке она вплотную примкнула к часовне: тогда здесь была устроена башня с воротами, получившими официальное имя «Никольские» по местной улице и «Владимирские» – по часовне. А потом, приблизительно в XVI в., список с Владимирской иконы поместили и на наружной стене Никольской башни Китай-города. Эта башня и оказалась на участке той самой эпохальной для Москвы Сретенской дороги... И царица Наталья Кирилловна Нарышкина решила построить тут церковь, освященную во имя Владимирской иконы. Ведь к тому времени не только в Москве, но и в этом историческом месте еще не было ни одного приходского храма в честь чудотворной иконы, а только Сретенский монастырь и часовня. И праздничные крестные ходы из Кремля совершались прямо в обитель. Царица дала обет – возвести здесь церковь. Причиной тому было не только знаменательное место – царица считала Владимирскую икону своей покровительницей, поскольку ее именины приходились на день праздника чудотворной иконы. И именно Владимирским образом родители царицы (по другим данным, ее воспитатель боярин Матвеев) благословили ее в день свадьбы с царем Алексеем Михайловичем в далеком 1671 г. Именно этот фамильный образ овдовевшая государыня и пожаловала царским подарком в новоустроенную церковь, хотя до освящения своего обетного храма ей дожить не довелось. Строительство красавицы-церкви в ярком, узорчатом стиле нарышкинского барокко было начато по личному указу Петра I, очень любившего мать, летом 1691 г. на казенные средства Стрелецкого приказа, а освящена она была в октябре 1694 г. Тогда к ней был установлен крестный ход из Кремля 21 мая – в празднование чудесного спасения Москвы от набега крымского хана в 1521 г.
Интересно вот что. Из-за своего местоположения церковь была приписана к Заиконоспасскому монастырю, что на Никольской улице, и именно его духовенство служило в этом обычном московском храме. Однако у Владимирской церкви не было и не могло быть своего прихода в торговом посаде Москвы, зато, как писал один дореволюционный краевед, у этой «бесприходной» церкви приходом была вся Москва, и каждый, кто шел по Никольской улице, непременно заходил в храм помолиться Заступнице рода человеческого и Спасительнице Москвы. Бесценные святыни Владимирской церкви соответствовали «дворцовому» статусу храма, возведенного по обету царицы. Она и стала его первой дарительницей, а вслед за Нарышкиной в эту китайгородскую церковь дарили и Елизавета Петровна, и Мария Федоровна – богатые пелены и воздухи, расшитые руками императриц. Образ Спаса Нерукотворного был, по преданию, написан в манере «фряжского письма» самим Симоном Ушаковым. Во второй половине XVIII в. архитектор Василий Баженов соорудил в храме огромный иконостас. Список Владимирской иконы в начале XIX в. украсила великолепная золотая риза с драгоценными алмазами, жемчугами, изумрудами и яхонтами – это был дар знаменитого графа Н.П. Шереметева по завещанию, так как прежний оклад храмовой чудотворной иконы был «легковесен». В церкви был и другой образ Владимирской Богоматери, в серебряном окладе, – тот самый, которым патриарх Иоаким благословил царицу Нарышкину на венчании с царем Алексеем Михайловичем. А в 1805 г. у церкви появилась и новая часовня, в которую поместили список иконы в красивой серебряной ризе, устроенной на пожертвование богатого москвича.