Название «Кулишки» связано со старинным районом Москвы, расположенным в месте слияния Москвы-реки и Яузы. Термин «кулишки» трактуется по-разному: как топкое, болотистое место или лес после порубки. В XV веке великий князь Василий I Дмитриевич построил здесь летний дворец с домовой церковью во имя святого князя Владимира. На склонах холма были разбиты княжеские сады, а рядом располагались государевы конюшни. При конном дворе была возведена деревянная церковь во имя святых мучеников Флора и Лавра, покровителей лошадей. Позднее, после строительства загородного дома московского митрополита в Трёхсвятительском переулке, к церкви Флора и Лавра был пристроен домовый митрополичий храм во имя Трёх Святителей Вселенских.
В 1674 году на средства прихожан был возведён новый каменный храм. Здание было двухэтажным с колокольней на углу. На нижнем этаже разместились тёплые приделы: Трёх Святителей с юга и Флора и Лавра с севера. Верхняя неотапливаемая часть была освящена в честь Святой Живоначальной Троицы. Фасады храма украсили узорные наличники и порталы, на верхний этаж вели высокие крыльца, а апсиды тёплых приделов завершались крытыми лемехом главами.
В XVIII—XIX веках храм претерпел ряд перестроек. В 1927 году храм был закрыт и передан в ведение Мясницкой тюрьмы. Церковные ценности были вывезены, а здание лишилось глав и шатра колокольни. В 1930-х годах здание использовалось различными организациями, включая НКВД, и было надстроено четвёртым этажом, превращаясь в коммунальное жильё. В 1950-х годах была разрушена ограда храма.
В 1960-х годах началась реставрация храма под руководством архитектора А. И. Окунева, целью которой было восстановление первоначального облика здания. Были воссозданы колокольня на углу, главы и декор фасадов XVII века. Сохранившаяся часть второй колокольни напоминает о поздних перестройках. С 1987 года в здании храма размещалась мультипликационная студия «Пилот».
В 1991 году была сформирована православная община храма. 30 июня 1992 года здание было возвращено Русской Православной Церкви. 6 июля 1996 года, в день празднования Владимирской иконы Божией Матери, в верхнем приделе во имя Живоначальной Троицы была отслужена первая литургия. В последующие годы были освящены приделы в честь Трёх Святителей Вселенских и преподобного Силуана Афонского.
