Первая деревянная церковь Похвалы на этом месте упоминается в исторических документах еще в 1475 г. – задолго до основания здесь монастыря. Алексеевский монастырь располагался на территории нынешнего Зачатьевского монастыря. Археологи утверждают, что ранние слои, предшествующие времени его строительства, не прослежены. По преданию, монастырь был основан митрополитом Алексеем. В списке построек Алевиза Нового от 1514 г. упоминается некая «церковь Алексея святый Человек Божей в девичи монастыре за Черторый». В деревянной же церкви Похвалы находилась чудотворная икона св. Николая, так что по чтимому образу иногда даже всю церковь именовали Никольской. От этой иконы произошло одно из древних названий московской церкви Похвалы – «старая проща». Дело в том, что в старину человека, исцелившегося от чудотворной иконы, называли
Деревянная церковь сгорела в 1629 г.; спустя какое-то время она была вновь отстроена, но уже из камня. В самом конце XVII столетия думный дворянин и печатник Дементий Минич Башмаков на свои средства и на пожертвование, завещанное подьячим Шандиным (для постройки нового здания подьячий Алексей Шандин, прежний прихожанин сгоревшей церкви, завещал значительную по тем временам сумму – 200 руб.), перестроил ее в том основном образе, в котором она и дожила до революции. Сам устроитель церковного здания Башмаков, чьи годы рождения и смерти неизвестны даже в наши просвещенные дни, считался известным государственным деятелем России 2-й половины XVII в. Дьяк с 1665 г., думный дьяк с 1676 г. и печатник (хранитель государственной печати) с 1688 г., Башмаков был еще и думным дворянином. Название «думные дворяне» употреблялось со 2-й половины XVI в. До этого они назывались «дети боярские думные», «дворяне у государя в думе», «дворяне, которые живут у государя с бояры». Думные дворяне участвовали в заседаниях Боярской думы, в работе ее комиссий, управляли приказами, выполняли придворные и военные обязанности, назначались воеводами в города. Некоторые из думных дворян дослуживались до чина окольничего и боярина. В XVI в. думные дворяне чаще всего принадлежали к родовитым фамилиям, и число их было невелико. В XVII в. с укреплением экономического и политического положения дворян и дальнейшей централизацией государственного управления число думных дворян увеличилось за счет неродовитых дворян и детей дьяков. Думные дворяне наряду с думными дьяками были опорой царской власти в борьбе с боярской аристократией в Боярской думе. В 1655–1700 гг. имя Башмакова упоминается в качестве служащего целых 16 приказов: Разрядного, Посольского, Большого дворца, Сыскного и др. При Алексее Михайловиче в 1658–1664 гг. этот разносторонний человек возглавлял даже Приказ тайных дел, где участвовал в следствии над участниками Московского восстания 1662 г. В 1672 г. Башмаков ненадолго перешел в дипломатическое ведомство и был отправлен с посольством в Польшу. Последний раз имя дьяка Башмакова упоминается в источниках в 1700 г.
Однако вернемся к храму и постараемся мысленно попытаться воссоздать его внешний вид. Высокий, пятиглавый, «старинной готической архитектуры и с готической архитектуры колокольней», как описывал его любитель ветхой древности; «в нем был не традиционный для большинства русских и московских церквей пятиярусный иконостас, а иконостас в шесть ярусов». Храмоздатель Дементий Башмаков, скончавшийся в 1705 г., был похоронен в приходе церкви Похвалы вместе с матерью и дочерью. И не только он один. С местными захоронениями связана одна из самых интересных и таинственных загадок не только этого храма, но и всей русской истории. Речь идет о могиле Малюты Скуратова. Как известно, Григорий Лукьянович (Малюта) Скуратов-Бельский погиб в бою при штурме ливонской крепости. По приказу царя тело Скуратова было отвезено в Иосифо-Волоцкий монастырь в Волоколамске. Родственники Малюты продолжали пользоваться царскими милостями, а вдова даже получала пожизненную пенсию, что было знаком исключительной царской милости в то время.