Historia naszego kościoła i Parafii jest ściśle związana z wydarzeniami Powstania Listopadowego, a szczególnie z rozegraną w pobliżu bitwą o Olszynkę Grochowską (25 lutego 1831 r.). Miejsca walk upamiętniał drewniany krzyż postawiony w 1916 roku. Jego poświęcenie stało się manifestacją patriotyczno - religijną z udziałem ok. 100.000 osób. Z czasem drewniany krzyż został zastąpiony metalowym (1931 r.); wmurowano także kamień węgielny pod budowę Pomnika - Mauzoleum. Obiekt ten nie powstał jednak do dnia dzisiejszego.
Pierwsza wzmianka o kościele, dotyczy drewnianej świątyni zbudowanej w końcu 1924 roku, przez pierwszego proboszcza Księdza Jana Sztukę. Parafię erygował 25 lutego 1925 roku, Kardynał Aleksander Kakowski. Tytuł kościoła nadała Księżna Radziwiłłowa. W Kronice parafialnej zapisano: "Księżna Maria Radziwiłłowa obrała tytuł kościoła <<Najczystsze Serce Maryi>>, ofiarowała parę koni, wóz, sporo bali okrągłych a po poświeceniu Kaplicy (pierwszego kościółka drewnianego) ofiarowała parę ornatów, kap, alb i komeż". Nie są do końca znane motywy nadania kościołowi właśnie tego tytułu. Być może Księżna - fundatorka kościoła pod wezwaniem <<Najświętszego Serca Jezusowego>> na Michałowie (dzisiejsza ulica Kawęczyńska) - chciała mieć w bliskim sąsiedztwie na Grochowie bliźniaczy kościół Serca Maryi. Według innej wersji, księżna jako osoba religijna, o szerokich kontaktach zagranicznych, mogła znać Objawienia Fatimskie, a tym samym jeden z warunków Matki Bożej - nabożeństwo do Serca Maryi - Jej Serca.
Obszerny plac pod budowę ofiarował mieszkaniec Grochowa, Jan Łaski - przedsiębiorca i budowlany, prezes Spółki Seryjnej Budowy Domów. W latach dwudziestych dyrygował sprawami parcelacyjnymi wielu dzielnic - szczególnie tych świeżo przyłączonych do stolicy.
Drewniana świątynia została postawiona w 6 tygodni, i przetrwała do 12 września 1944 roku. Spłonęła, kiedy wojska radzieckie zajmowały Pragę.
Szybki przyrost ludności na Grochowie spowodował konieczność budowy większej świątyni. Członkowie Towarzystwa Przyjaciół Grochowa zdecydowali o budowie kościoła - pomnika dla uczczenia pamięci bohaterów poległych w bitwie o Olszynkę. Jednocześnie w 1931 roku, w setną rocznicę Powstania Listopadowego, Komitet Budowy Kościoła - Pomnika poległych za Ojczyznę, podjął działania w celu gromadzenia funduszy i materiałów. Wystosowano odezwę do narodu o wsparcie finansowe. Organizowano uroczyste akademie i występy artystów polskich. Urządzano loterie i zabawy, a parafianie kwestowali z puszkami na ulicy.
Wreszcie, 10 czerwca 1934 roku, poświęcono kamień węgielny, a budowę w stanie surowym, według projektu architekta Andrzeja Boniego, ukończono w roku 1941.
Organizatorem, budowniczym i pierwszym proboszczem parafii był, aż do swojej śmierci 26 grudnia 1970 roku, Ksiądz Jan Sztuka.
Podczas kopania fundamentów, natrafiono na dwie zbiorowe mogiły powstańcze. Podobnych mogił na terenie Grochowa znajdowano wtedy wiele. Prochy poległych umieszczano w symbolicznym grobowcu na Olszynce Grochowskiej.
W czasie okupacji trwały prace wykończeniowe przy świątyni. Zostały one przerwane w momencie wybuchu Powstania Warszawskiego. Kościół, na szczęście, nie ucierpiał wiele w czasie wojny. Jedyne straty to nieznacznie uszkodzony dach i mury od strony północnej. Niemcy planowali wysadzenie budynku - nie zdążyli jednak zrealizować swoich planów.
Konsekracji kościoła dokonał Kardynał Stefan Wyszyński, w dniu 30 października 1949 roku. Z dniem 1 stycznia 1950 roku, wraz z utworzeniem parafii św. Wacława, pamiątkowy krzyż z 1931 roku, znalazł się w jej granicach, ale w kościele Najczystszego Serca Maryi, 25 lutego, co roku, składane są kwiaty pod pamiątkowymi tablicami. Jedną z nich w 130 rocznicę Powstania Listopadowego (1961 r.), ufundowali parafianie. Można ją zobaczyć w kruchcie nawy głównej. W krużgankach kościoła znajdują się natomiast cztery inne tablice pamiątkowe: 2., 3., 4., i 5. pułku ułanów biorących udział w bitwie pod Olszynką.
Miejsce wiecznego spoczynku w wybudowanym przez siebie kościele, znalazł także Proboszcz Ksiądz Jan Sztuka. Jego krypta grobowa znajduje się pod kaplicą nawy bocznej, przy ołtarzu Matki Boskiej Częstochowskiej.