История храма тесно связана с Ямской Коломенской слободой, возникшей в XVII веке. В 1625 году, после переноса ямщиков с Полянки на Зацепу, была построена деревянная церковь во имя святых мучеников Флора и Лавра, покровителей коневодов и ямщиков.
В 1737 году деревянная церковь была уничтожена пожаром. В 1739 году было получено разрешение на строительство каменного храма, который был завершён в том же году. Главный престол нового храма был освящён в честь иконы Божией Матери «Всех Скорбящих Радость», а придел — во имя святых мучеников Флора и Лавра.
В 1835 году по проекту архитектора Ордерова (Орденова) в стиле ампир были перестроены приделы, трапезная и колокольня. В 1861–1862 годах был перестроен основной объём церкви, что придало храму современные архитектурные формы. В 1909 году к храму были добавлены западные пристройки, расширившие его пространство.
В 1924 году, после закрытия многих московских церквей, в храм святых мучеников Флора и Лавра на Зацепе начали переносить церковную утварь, иконы и святыни, включая иконы из взорванного храма Христа Спасителя. Однако в 1938 году храм был официально закрыт, здание осквернено и передано под цех фабрики металлографических и граверных работ. Внутри были возведены перегородки и межэтажные перекрытия, настенные росписи закрашены и частично уничтожены, а главка над основным объёмом церкви разобрана. В 1957 году колокольню пытались взорвать, но основание устояло, разрушились только верхние ярусы.
В 1960 году здание храма было признано памятником архитектуры и поставлено под государственную охрану, однако его продолжали использовать под производственные цели. В 1978 году начались исследовательские и проектные работы по реставрации храма, в частности, к 1985 году был создан проект восстановления колокольни и главки, однако эти работы не были реализованы.
Решение о передаче храма Русской Православной Церкви было принято 8 января 1991 года. Для проведения богослужений был расчищен один из производственных цехов, и на Пасху 6 апреля 1991 года состоялось первое богослужение. Окончательно производство было остановлено только к августу того же года из-за нарушения экологических и пожарных норм. Территория вокруг храма была очищена от алюминиевых отходов, а под алтарём придела святых мучеников Флора и Лавра было снято около 2 метров земли, так как фабрика сливала отходы производства в отверстия под фундамент.
К 1997 году были восстановлены барабан и главка над куполом церкви, верхние ярусы колокольни, а также проведены некоторые другие реставрационные работы. Второй этап реставрации был проведён с 2010 по 2018 год, в 2015–2016 годах — с привлечением субсидий московского бюджета. В ходе работ на фасаде обновили главу, крест, световой барабан, ротонду, портики, северную и южную паперти, воссоздали лепной декор и нанесли защитную штукатурку, воссоздали монументальную живопись, полностью утраченную в советский период. В куполе появилась уникальная система деревянных стропил, устроены гидро- и пароизоляция, а также утепление кирпичной кладки свода. В главном входе и притворе заменили большинство деревянных деталей, а в самом храме — деревянное покрытие пола на гранитные плиты.
Архитектурно храм представляет собой образец русского классицизма с элементами ампира. Основной объём храма — это ротонда с куполом, окружённая колоннадой, что придаёт зданию монументальность и величественность. Колокольня, восстановленная после разрушения, гармонично дополняет общий архитектурный ансамбль.
