В начале 1930-х годов Государственное акционерное общество по иностранному туризму в СССР «Интурист» было слито со Всесоюзным акционерным обществом «Отель», в результате чего получило несколько гостиниц, ресторанов и большое количество автотранспорта. Тогда было принято решение о строительстве отдельного гаража для «Интуриста».

Над проектом гаража совместно трудились группа проектировщиков Гипроавтотранса и мастерская Моссовета №7, возглавляемая всемирно известным русским архитектором Константином Мельниковым. В 1933 году в инженеры-технологи Гипроавтотранса создают типовое решение пятиэтажного гаража с полурампами на 300 автомобилей. От мастерской Мельникова требовалось лишь архитектурное оформление фасадов.

Обычно Константин Степанович работал один, выполняя все чертежи самостоятельно, но в этот раз он подключил к работе помощника: «Технологической сути я почти не касался, предоставив вести это, а также и разработку рабочих чертежей своему весьма исполнительному сподвижнику В.И. Курочкину, занявшись сам рисовкой архитектуры внешних форм…». Мельников смело меняет композицию фасада, создавая динамическую композицию из простых геометрических фигур. Правую частью фасада он решает большими остекленными плоскостями – круг и трапеция. Левая часть – равномерное членение вертикальными окнами. Основная композиционная ось – диагональ, именно она «разрезает» плоскость фасада на две части. Начинаясь от низа круга, она «летит» вверх и огибает здание слева полуциркульной консолью, намекая на символ бесконечности. "Путь туриста изображен бесконечностью, – писал Мельников – начиная его с размаха кривой и направляя его быстрым темпом вверх в пространство".

По замыслу архитектора, вход в здание должен был находиться с угла здания, над ним – скульптурная композиция, еще выше – полукруглая консоль-козырек, на фасаде в верхней части – логотип «Интуриста», а на диагонали – закреплен настоящий автомобиль!

К сожалению, проект архитектора был реализован лишь частично: правая сторона фасада с большим круглым окном. Левую часть здания строили уже без Мельникова: пятиэтажной, в набиравшем обороты неоклассическом стиле.

За время существования здание гаража несколько раз перестраивалось. С 1990 года признано объектом культурного наследия регионального значения. В настоящее время принадлежит Автотранспортной службе Управления материально-технического обеспечения ФСБ.