Первый храм Флора и Лавра была построена в XVI в. на территории
слободы в районе Полянки, где жил Ямущик. Святые Флор и Лавр
почитались на Руси как покровители домашнего скота, в том числе
лошадей, и профессий, связанных со скотом, таких как скототорговцы,
пастухи, конюхи и кучера В 90-х годах XVII века Слобода была
перенесена в район, известный как Зацепа. Вход в нее был перегорожен
цепями, перед которыми досматривались повозки для выявления товаров
и грузов, ввозимых в столицу в обход таможни.
Обосновавшись
на новом месте, подводы вновь построили церковь в честь своих
покровителей. Однако в честь Флора и Лавра был посвящен только
боковой неф, а по главному алтарю церковь была названа
Петропавловской; известно, что в первой половине XVIII в. в церкви
имелся также боковой алтарь во имя святителя Николая, который в 1738
г. сгорел, а на его месте было устроено временное церковное
подворье, после чего был построен каменный двор, был построен
каменный церковный двор. Примерно в это же время главные алтари
церквей во Флорасе и Лаурасе были освящены в честь иконы Божией
Матери "Всех скорбящих Радость", которая и по сей день является
официальным названием храма.
В течение XIX века храм был
перестроен, приняв свой нынешний вид в стиле московского ампира. В
конце следующего столетия, в конце 30-х годов, храм был закрыт
большевиками, но до этого, с середины десятилетия, он стал местом
хранения реликвий и церковной утвари, перенесенных из других
разрушенных или закрытых церквей В первой половине XX века, во
времена правления реноваторов, храм был снесен, возведены уродливые
перекрытия и внутренние перегородки, колокольня Здание храма
подвергалось всевозможным надругательствам, в том числе разрушению
верхней части.
После ряда разрушений храм был признан
объектом архитектурного наследия, была разработана программа
реставрации, однако в советский период реставрационные работы не
проводились, а после передачи храма РПЦ в 1990-х годах были
проведены реставрационные работы.