В письменных источниках церковь упоминается с 1625 г. как приходская церковь дворцовой Большой Конюшенной слободы, расположенной на этом месте со времен Ивана Грозного. Св. Власий издавна почитался на Руси как покровитель домашних животных, на него перенесли верования, связанные с языческим богом Велесом. Недаром эта церковь стояла в Конюшенной слободе и называлась «что в Старой Конюшенной», а по старым документам — «на Козьем болоте». Постепенно слобода была вытеснена за пределы Земляного города и место получило название Староконюшенной.
Первые документальные сведения о каменном храме относятся к 1644 г. Одноглавую кирпичную церковь построили на месте старой с главным престолом Преображения Господня и Казанским, Власьевским и Никольским (позже упраздненным) приделами. Но в некоторых документах конца ХVII века храм упоминают как «церковь Василия, что была на козьем болоте», а на плане Москвы Горихвостова 1767 г. как «Васильевский» храм.
Свой современный вид церковь приобрела в результате многократных перестроек: ХVII в. — появление первой трапезной, XVIII в. — возведение колокольни, в первой половине ХIХ в. была создана новая апсида, а в 1866-1872 гг. на средства купца Куманина — новая широкая трапезная с приделом Казанской божьей Матери. В 1880 г. установлен новый главный иконостас, сделанный по рисунку А. Каминского.
Объём небольшого одноглавого четверика храма почти целиком относится к 1644 г., а его декор, выполненный в духе московского барокко, — к концу XVII в. Составленный из разновременных объемов, памятник тем не менее представляет композицию, традиционную для допетровской эпохи. В 1921 г. был освящен престол Серафима Саровского, перенесенный сюда из ликвидированной домовой церкви Серафимовского комитета Красного Креста на Сивцевом Вражке. В 1939 г. церковь была закрыта, обезглавлена, внутри разместились школьные мастерские.
Много лет храм был в полном небрежении, пока, наконец, не был приведен в относительный порядок силами общественности и в 1992 г. передан верующим. Литургии служатся с 1997 г. В храме сохранились фрагменты росписей XVII в.