И «в Палашах» означает именно «в Палашах», то есть в слободе оружейников, ковавших палаши, сабли и прочее холодное оружие (отметим, что на такой трактовке названия урочища настаивал еще И.К. Кондратьев в 1893 году). Не случайно ведь по соседству находилась Бронная слобода. О Палашевской слободе напоминают доныне Большой и Малый Палашевские переулки возле Тверской улицы. Большой Палашевский переулок в старину называли по храму Рождественской улицей.

Слободская церковь Рождества Христова стояла в Малом Палашевском переулке, 3. Она известна в слободе с начала XVI века. Традиционно считается, что построена церковь была в 1573 году по указу Ивана Грозного. Перестроенная в XVII—XVIII веках, она приобрела вид типичного посадского храма XVII века, с пятиглавием и шатровой колокольней (пристроена в 1б44году). Однако «Строельная книга» Москвы 1657 года фиксирует здесь деревянный храм. Источники говорят об освящении каменной церкви в феврале 1692 года.

Но это может быть и датой освящения после перестройки. Как бы то ни было, здание церкви, сохранявшееся до XX века, вполне характерно для храмовой архитектуры середины XVII столетия. В XVII—XIX веках храм именовали еще — «в Старых Палашах», что означает, что слобода со временем переехала. Ее дворы заняли жители Новоникитской слободы. Прихожанином церкви Рождества в Палашах был замечательный архитектор XVIII столетия Дмитрий Ухтомский, автор знаменитых Красных ворот.

После французского погрома 1812 года церковь отстроили к 181 5-му. В 1836 году к ней пристроили новую трапезную, в которую перенесли приделы Взыскания погибших (известен с 1815 года, сменил существовавший до него Покровский) и Николая Чудотворца (с 1722 года). С запада перед храмом стояли парные пилоны ампирных ворот XIX века.

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