В 1894 году совет Римско-католической церкви свв. Петра и Павла в Милютинском переулке обратился к московскому губернатору с просьбой разрешить строительство третьего католического храма. Разрешение было получено при условии строительства вдалеке от центра города и особо почитаемых православных храмов, без башен и наружных изваяний. Неоготический проект Ф. О. Богдановича-Дворжецкого, рассчитанный на 5000 молящихся, был утверждён, несмотря на несоблюдение последнего условия.
Католический храм на Малой Грузинской на карте Москвы 1907 года:
Основной объём храма был построен в 1901—1911 годах. Деньги на строительство были собраны польской общиной, численность которой в Москве в конце XIX века достигала 30 тысяч человек, и католиками других национальностей по всей России. Ограда собора сооружена в 1911 году по проекту архитектора Л. Ф. Даукша.
Храм, получивший название филиальной церкви Беспорочного Зачатия Пресвятой Девы Марии, был освящен 21 декабря 1911 года.
Строительство храма обошлось в 300 тысяч рублей золотом, дополнительные суммы были собраны в 1911—1917 годах на отделку и приобретение церковных принадлежностей. Отделочные работы внутри храма продолжались до 1917 года.
В 1919 г. филиальная церковь была превращена в полноценный приход. Его настоятелем стал 34-летний священник о. Михал Цакуль (1885—1937).
В 1938 году храм был закрыт, церковное имущество разграблено, а внутри было организовано общежитие. Во время войны здание пострадало от бомбардировок, были уничтожены несколько башенок и шпилей. В 1956 году в храме расположился НИИ «Мосспецпромпроект». Была произведена перепланировка здания, полностью изменившая интерьер церкви, в частности, основной объём внутреннего пространства был поделён на 4 этажа. В 1976 году был разработан проект реставрации здания, где предполагалось разместить зал органной музыки, но этот проект так и не был реализован.
В 1989 г. культурная ассоциация «Дом Польский», объединяющая московских поляков, поставила вопрос о необходимости возвращения здания храма его естественному владельцу — Католической Церкви. В январе 1990 г. группой московских католиков был образован польский католический приход Непорочного Зачатия Пресвятой Девы Марии. 8 декабря 1990 года, по случаю праздника Непорочного Зачатия Пресвятой Девы Марии, о. Тадеуш Пикус (ныне епископ) с разрешения властей впервые после 60-летнего перерыва отслужил мессу на ступенях собора. На этой первой службе присутствовало несколько сот человек. Постоянные богослужения стали проводиться с 7 июня 1991 года.
В 1996 году, после длительного скандального выселения НИИ «Мосспецпромпроект», храм был передан Католической Церкви. На протяжении нескольких лет в храме были проведены масштабные реставрационные и восстановительные работы и 12 декабря 1999 года Государственный секретарь Ватикана кардинал Анджело Содано торжественно освятил отреставрированный Кафедральный собор.