В XVII веке переулок у церкви, отходящий от Маросейки, назывался по храму — Козьмодемьянским (Космодамианским), он сохранял такое название до 1922 года. Сейчас это Старосадский переулок.

Точных сведений, когда впервые была построена церковь, не имеется. Но впервые деревянный храм на месте нынешнего упоминается во время пожаров в 1547 и 1629 годах. Упоминание старой каменной церкви относится к летописи 1639 года.

В конце XVIII века старая церковь сильно обветшала, поэтому на её месте было принято решение построить новый храм — ныне существующий. Церковь возвели в 1793 году по проекту московского архитектора Матвея Казакова. Строительство велось на средства владельца дома, стоявшего по другую сторону улицы — М. Р. Хлебникова (сейчас в этом доме находится Посольство Республики Беларусь).
В 1812 году Космодамианская церковь лишилась значительной части своего имущества и украшений. И лишь в 1893 году она была основательно отремонтирована прихожанами.

Церковь Космы и Дамиана, как и многие московские храмы, была закрыта в конце 1920-х годов. Тогда же вышло постановление снести ограду, чтобы расширить дорогу. И уже в начале 1930 годов планировалось снести и саму церковь полностью, но в итоге храм удалось спасти. Здание церкви использовалось как производственный склад, затем в 1950—1960-х годах внутри размещалась макетная мастерская. В 1958 году на фасадах церкви была проведена научная реставрация, восстановлены золочёные главы и кресты. Интерьер храма тогда так и остался перестроенным. В 1972 году вокруг церкви была возведена новая ограда, похожая на прежнюю.

Храм был возвращен Русской православной церкви в 1993 году. В том же году в день памяти святых бессребреников Космы и Дамиана в правом приделе состоялась первая Литургия. Постепенно были разобраны советские перекрытия и восстановлены первоначальные интерьеры церкви. Возведён новый центральный иконостас и восстановлены иконостасы приделов.