Село Котельники впервые упоминается в начале XVII века. В 1651 году оно было приобретено боярином Борисом Ивановичем Морозовым, при котором в селе уже существовала деревянная церковь в честь Казанской иконы Божией Матери. После смерти в 1676 году его супруги, боярыни Феодосии Морозовой, село перешло в царское ведомство. В период с 1675 по 1680 годы мастера Каменного приказа возвели новую каменную пятиглавую церковь на высоком подклете. В августе 1685 года храм был освящен патриархом Иоакимом в присутствии царей Петра и Иоанна Алексеевичей, а также их матери, царицы Натальи Кирилловны Нарышкиной. Согласно преданию, именно она пожертвовала храму список Казанской иконы Божией Матери, ставший главной святыней церкви.
Архитектурно храм представляет собой образец московской архитектурной школы XVII века, положившей начало формированию стиля «русское барокко». Здание возведено на высоком холме, являющемся одной из самых высоких точек в окрестностях Москвы, с высотой подножия около 170 метров над уровнем моря.
В первой половине XIX века по проекту архитектора Алессандро Жилярди была построена колокольня, дополнившая архитектурный ансамбль храма.
В 1922 году из церкви была изъята часть церковной утвари, включая ризу с Казанской иконы Божией Матери, украшенную жемчугом, изумрудами и алмазами. В 1938 году храм был закрыт, а в начале 1940-х годов с него сняли главы, колокольню частично разобрали, и в 1957 году на ее месте установили резервуар для воды. В 1960 году храм получил статус памятника архитектуры республиканского значения, однако реставрационные работы не проводились.
В 1990 году храм был возвращен Русской Православной Церкви и начались работы по его восстановлению. К настоящему времени храм полностью отреставрирован и вновь открыт для прихожан.
