Gwiaździsty plac Zbawiciela stanowił pierwotnie element ogrodu na osi królewskiej rezydencji ujazdowskiej. Jednak rozwijające się miasto nieuchronnie wchłaniało parkowe niegdyś tereny. W 1829 na miejscu dzisiejszego kościoła postawiono karczmę. Po 1880 plac zabudowano kamienicami i przeprowadzono przezeń linię tramwaju konnego. W końcu XIX w. liczba mieszkańców dzielnicy zajmującej dawne ogrody królewskiej rezydencji ujazdowskiej wymagała budowy nowej, obszernej świątyni. Zdecydowano, że będzie ona wotum dla Zbawiciela na rok święty 1900.
Kościół wzniesiono według projektu zespołu architektów: Józefa Piusa Konkurs architektoniczny wygrał projekt Stefana Szyllera, jednak kościół wzniesiono według projektu zespołu architektów: Józefa Piusa Dziekońskiego, Ludwika Panczakiewicza i Władysława Żychlewicza. Kamień węgielny (widoczny dziś przy oknie za ołtarzem dolnego kościoła) wmurowano 12 października 1901. Poświęcił go arcybiskup warszawski Wincenty Popiel. Parafia została erygowana 1 stycznia 1911. Wskutek I Wojny Światowej prace budowlane trwały długo i dopiero 23 października 1927 konsekracji kościoła dokonał arcybiskup Stanisław Gall. Do wyposażenia przyczynili się najlepsi warszawscy artyści, m.in. architekt Stefan Szyller i rzeźbiarz Pius Weloński.
Kościół jest trójnawową bazyliką z obszerną nawą poprzeczną (transeptem) i kopułą na skrzyżowaniu naw. Jego styl nawiązuje do form polskiego renesansu i baroku. Nad skrzyżowaniem naw istniała pierwotnie dwudziestometrowa wieża sygnatury. Usytuowanie na trójkątnej działce miało decydujące znaczenie dla ukształtowania bryły i układu przestrzennego kościoła, umożliwiając wzniesienie kaplicy Matki Bożej od strony Marszałkowskiej i symetrycznie, obszernej zakrystii od strony Mokotowskiej. Główna fasada kościoła od strony placu, w formie kolumnowego portyku, flankowana jest dwiema wysmukłymi wieżami. Zdobią ją monumentalne rzeźby św. Piotra i św. Pawła.
We wrześniu 1939 podczas bombardowania Warszawy pociski zwaliły sygnaturę, zachodnią wieżę i dach. Jednak największym zniszczeniom uległ kościół w roku 1944, gdy po upadku Powstania Warszawskiego Niemcy przystąpili do systematycznego burzenia domów i świątyń. U Zbawiciela podłożyli materiał wybuchowy w kościele dolnym i wysadzili go w przeddzień ucieczki ze Stolicy. Runęły sklepienia, hełm drugiej wieży i kościół dolny. Nadzwyczaj silna konstrukcja filarów i arkad sklepiennych wytrzymała jednak ten wstrząs.
Po zabezpieczeniu zrujnowanej świątyni prowizorycznym dachem przesklepiono podziemie oraz naprawiono okna i drzwi aby oddać kościół do użytku. Główne sklepienia odbudowano później. Podczas budowy Marszałkowskiej Dzielnicy Mieszkaniowej, w 1952 władze komunistyczne nakazały przesunięcie osi ulicy Marszałkowskiej, aby zasłonić widok na kościół. Długo też trwało uzyskiwanie zezwolenia na odbudowę wież, które przywrócono dopiero w 1955.
Dekretem kard. Józefa Glempa, Prymasa Polski z 2006 roku, kościół Najświętszego Zbawiciela został podniesiony do rangi Sanktuarium Matki Zbawiciela. Wcześniej w 1999 roku św. Jan Paweł II koronował na Placu Piłsudskiego Cudowny Obraz Matki Zbawiciela koronami papieskimi.
Parafia od początku aktywnie współpracuje z największą uczelnią techniczną w kraju – Politechniką Warszawską, której siedziba znajduje się na terenie Parafii. Kościół Najświętszego Zbawiciela pełni rolę kościoła akademickiego tej uczelni i jest siedzibą Duszpasterstwa Akademickiego „Sandał”.
Parafią Najświętszego Zbawiciela zarządzali kolejno:
Ksiądz Prałat Roman Rembieliński (1911-1926)
Ksiądz Prałat Marceli Nowakowski (1926-1939)
Biskup Wacław Majewski (1946-1983)
Ksiądz Prałat Bronisław Piasecki (1983-2010)
Ksiądz Prałat Tadeusz Sowa (2010-2018)
Ksiądz Kanonik Robert Strzemieczny (od 2018)