Parafię erygował kard. Aleksander Kakowski 8. grudnia 1934 r. Obejmowała część terenów Józefowa, Wiązowny, Radości i Zerzenia. Powstała dzięki usilnym staraniom mieszkańców Falenicy, którzy wielkim wysiłkiem doprowadzili do budowy kościółka-kaplicy pod wezw. Najświętszego Serca Pana Jezusa.. Działkę pod budowę, ok. 0,5 ha, na wydmie zw. Górne ofiarował właściciel folwarku Błota Karol Hanneman. Do tej pory Faleniczanie-katolicy należeli do parafii w Józefowie. Tamtejszy proboszcz, ks. Mieczysław Królak stanął na czele Komitetu Budowy Kościoła, który po budowie częściowo wyposażył. Najpierw, na poziomie ulicy (wtedy Różana, potem Kościelna) postawiono jednopiętrową organistówkę (1929), w której zamieszkał dozorca, a następnie organista, Jan Marcinkiewicz z rodziną (do 1963 r.); potem była siedzibą wikariuszy (do 1990 r.). Budowa drewnianej kaplicy (1930–1932) kosztowała 30 tys. zł. Na ten cel zaciągnięto pożyczki u osób prywatnych, stowarzyszeń i parafii józefowskiej. Poświęcenia dokonał ks. Królak 26 lutego 1933 r. Msze św. odprawiano w niedziele, tylko w okresie letnim (kościółek był nieogrzewany). Ks. Królaka zastąpił ks. Jan Rozbiewski, przed którym postawiono zadanie organizacji parafii. W 1936 r. zakończono budowę drewnianej plebanii.

W 1924 r. Wille Falenickie, które przejęły nazwę od małej osady rybackiej nad Wisłą, stały się centrum Gminy Letnisko-Falenica sięgającej od Świdra po Międzylesie. Falenica szybko zwiększała liczbę ludności, zwłaszcza w okresie letnim, gdy zjeżdżali tu letnicy. W 1936 r. na ok. 9 tys. jej stałych mieszkańców ok. 5 tys. było wyznania mojżeszowego, 2420 – rzymsko-katolickiego, 1400 – ewangelickiego. Wkrótce okazało się, że kaplica, przewidziana na 400 osób, była niewystarczająca dla mieszkańców wyznania rzymsko-katolickiego. Plan budowy murowanego kościoła podjął nowy (od 1938 r.) proboszcz Sylwester Szulczyk, który zaczął już nawet gromadzić materiały budowlane. Zamiary te udaremniła wojna. Podczas Bitwy Falenickiej (19 września 1939 r.) budynki kościelne poniosły znaczne szkody. Po wojnie ks. Szulczyk rozpoczął starania o pozwolenie na budowę kościoła murowanego, ale, ze względu na odmowę władz PRL, przyjął metodę obudowania kaplicy murami nowego kościoła (wg projektu S. Czarneckiego i J. Skopińskiego). Budowa trwała w latach 1951–1959, a po usunięciu kaplicy aż do 1967 trwały prace wykończeniowe. W budowie – fizycznie i finansowo – brało udział wielu mieszkańców Falenicy.

W latach 1963–1967 proboszczem parafii był ks. dr Marian Kalinowski, a w latach 1967–1986  ks. dr Henryk Chudek. Z jego inicjatywy powstał nowy wystrój wnętrza kościoła wykonany przez artystę Zbigniewa Łoskota: polichromia w absydzie przedstawiającą Chrystusa z apostołami, płaskorzeźby trojga świętych, mozaiki Drogi Krzyżowej, boczny ołtarz i 47 witraży. Konsekracji - poświęcenia kościoła dokonał Kard. Stefan Wyszyński w dniu 31 sierpnia 1974 roku. Ks. Chudek doprowadził też do wzniesienia murowanej dzwonnicy upamiętniającej wybór Jana Pawła II (1980)  i kaplicy przy cmentarzu w Aleksandrowie oraz rozpoczął budowę Domu Parafialnego (1984–1990). Kolejni proboszczowie to ks. Andrzej Kamiński (1986–1993) i ks. Andrzej Dybek (1993–1999), który rozpoczął starania o urządzenie nowego cmentarza. Dzięki jego staraniom dach kościoła pokryto blachą miedzianą (1994). W czasie gdy proboszczem był ks. Marek Doszko (1999–2006) zaczęto wydawać „Wiadomości parafialne”, a nad wejściem do kościoła umieszczono mozaikę autorstwa Pawła Przyrowskiego (w technice weneckiej), przedstawiającą Chrystusa Pantokratora (2001).  Ks. Doszko zlecił budowę groty Matki Bożej z Lourdes (2006) i generalny remont schodów. W parafii zaczął działać chór Flaminae pod kierownictwem Marty Wiatr. Ks. Doszko zezwolił na uruchomienie w Domu Parafialnym ogniska TPD, wspierał koncerty Falenickiego Towarzystwa Kulturalnego i Parafialny Klub Sportowy. W latach 2006–2013 proboszczem był ks. Krzysztof Pietrzak, który wznowił zwyczaj wydawania posiłków dla osób biednych i AA. Po nim administratorem parafii został ks. dr Wiesław Kazimieruk. Z jego inicjatywy, w 80. rocznicę powstania parafii, odbyły się misje parafialne i uroczysta msza św. z udziałem abp. Henryka Hosera 6 grudnia 2014 r. W 2022 r. funkcję proboszcza parafii NSPJ w Falenicy objął ks. Krzysztof Węglarz.

Szczegółowa historia powstawania parafii, budowy kaplicy, a następnie kościoła została przestawiona w monografii Barbary i Zbigniewa Wizimirskich pt. „Jubileusz 75 lecia parafii NSPJ w Falenicy 1934–2009”. Książka jest dostępna w bibliotece falenickiej. Tam też czytelnik znajdzie dokładne opisy architektury i wewnętrznego wystroju nowego kościoła w tym objaśnienia co do treści witraży oraz spis wikariuszy i prezentacje działających wówczas grup parafialnych.