Myśl o wybudowaniu narodowego wotum powstała po uchwaleniu Konstytucji 3 Maja. Już 5 maja 1791 r. Sejm Czteroletni zdecydował, żeby jako wyraz wdzięczności za konstytucję, Bożą opiekę i prowadzenie „kościół ex voto wszystkich stanów był wystawiony i najwyższej Opatrzności poświęcony”. Zgodnie ze wskazaniem Stanisława Augusta Poniatowskiego, świątynia miała powstać na terenie obecnego Ogrodu Botanicznego w Warszawie, według projektu Jakuba Kubickiego. Do dziś zachowały się resztki fundamentów i kielnia, którą sam król Poniatowski rozpoczął budowę. W realizacji planów przeszkodził trzeci rozbiór Polski w 1795 r.

Do planów powrócono w 1921 r., kiedy ówczesny Sejm potwierdził wolę wykonania ślubu uczynionego przez Sejm Czteroletni. Na publiczny konkurs na projekt świątyni napłynęło 50 prac. Zwycięskie koncepcje nie zyskały jednak akceptacji Episkopatu Polski. W kolejnym konkursie w 1930 r. spośród 15 zgłoszonych prac jednomyślnie wybrano projekt Bohdana Pniewskiego. Tym razem świątynia miała stanąć na Polach Mokotowskich. Latem 1939 r. wmurowano nawet kamień węgielny, ale wybuch II wojny światowej uniemożliwił budowę.

Tuż po wojnie w otoczeniu prymasa Polski kard. Augusta Hlonda próbowano podjąć na nowo sprawę budowy świątyni. Śmierć prymasa i okres panowania reżimu stalinowskiego na długi czas zniweczyły te plany. Przy poparciu kard. Stefana Wyszyńskiego, po 23 latach starań, na Rakowcu stanął kościół Opatrzności Bożej. Konsekrując go 8 grudnia 1979 r., prymas powiedział: „Bóg przyjmie zamiast niespełnionych ślubów narodu naszą zastępczą ofiarę tej świątyni, budowanej z niezwykłym trudem, z ogromnym poświęceniem, z wytrwałością, cierpliwością, z bohaterskim zaparciem się siebie”.

Dopiero w 1991 r., w 200. rocznicę uchwalenia Konstytucji 3 Maja, Senat uznał, że zobowiązanie złożone po jej uchwaleniu jest nadal aktualne i należy je zrealizować również dla upamiętnienia pontyfikatu papieża Jana Pawła II. Pięć lat później, w czasie obchodów 400-lecia stołeczności Warszawy, kard. Józef Glemp, prymas Polski, przypomniał o narodowym zobowiązaniu. Poparły go władze stolicy i Konferencja Episkopatu.

Sejm, uchwałą z 23 października 1998 r., stwierdził, że „śluby złożone przed dwustu laty naród powinien pilnie wypełnić”, a świątynia będzie symbolem wdzięczności narodu za odzyskanie wolności w 1989 r., 20 lat pontyfikatu Jana Pawła II, jubileusz 2000-lecia chrześcijaństwa. Miejsce na nią wyznaczono na Polach Wilanowskich. Kardynał Glemp powołał Fundację Budowy Świątyni Opatrzności Bożej.

Na rozpisany rok później konkurs na projekt świątyni napłynęło 101 prac, a spośród 3 zwycięskich kard. Glemp wybrał do realizacji koncepcję Marka Budzyńskiego. Przedstawiała przyszły kościół jako symboliczną górę, pokrytą trawą i zwieńczoną kryształowym świetlikiem. Nowatorski pomysł był mocno krytykowany, istniały też obawy o wysokie koszty późniejszego utrzymania budowli. 2 maja na terenie przeznaczonym pod budowę świątyni ustawiono 7- metrowy krzyż. Prymas Glemp wyraził nadzieję, że ten dzień - jako wigilia rocznicy Konstytucji 3 Maja i święta Matki Bożej Królowej Polski - pozostanie w kalendarzu liturgicznym jako święto Opatrzności Bożej.

W 2001 r. w drugim, zamkniętym konkursie na projekt świątyni wybrana została propozycja Wojciecha i Lecha Szymborskich. Rok później 2 maja uroczyście wmurowano kamień węgielny, pobłogosławiony przez papieża Jana Pawła II podczas pielgrzymki do Polski w 1999 r. Wykonawcą kompleksu świątynnego została firma Marciniak SA z Gorzowa Wlkp. 30 stycznia 2003 r. ówczesny prezydent Warszawy Lech Kaczyński przekazał prymasowi pozwolenie na budowę świątyni. 23 lutego rozpoczęły się prace budowlane. Wkrótce jednak, ze względu na brak pieniędzy, budowa stanęła.

W 2007 r. nowy metropolita warszawski kard. Kazimierz Nycz ustanowił obchodzony w całym Kościele Dzień Dziękczynienia, który stał się zachętą do włączenia się wszystkich rodaków w budowę świątyni. Cztery lata później ukończono tzw. stan surowy otwarty, oddano do użytku Panteon Wielkich Polaków. Na szczycie kopuły zamontowano ponadpięciometrowy krzyż.

W lipcu tego roku, podczas Mszy posłania na Światowe Dni Młodzieży, po raz pierwszy wierni, wchodząc przez Bramę Miłosierdzia, zobaczyli wnętrze świątyni.