Starania o pozwolenie na budowę kaplicy na osiedlu Pieścirogi Stare /oddalonym 4 km od Nasielska, przy stacji PKP/ rozpoczął Biskup Bogdan Sikorski w latach 70 -tych. Dopiero jednak pod koniec lat 80 -tych, a konkretnie w 1989 roku, kiedy paskudny komunizm miał się ku końcowi, pod naciskiem mieszkańców osiedla, uzyskano pozwolenie na budowę kaplicy katechetycznej.


13 lipca 1990 roku rozpoczęto wykopy pod fundamenty kaplicy. Zaangażowanie mieszkańców osiedla było tak duże, że już 29 września /po dwóch miesiącach/ została odprawiona w kaplicy pierwsza Msza święta.
W marcu 1991 roku, na prośbę dziekana nasielskiego, Biskup Zygmunt Kamiński utworzył, przy nowo wybudowanej kaplicy, samodzielny ośrodek duszpasterski. W kwietniu 1991 roku została erygowana parafia p.w. św. Katarzyny Aleksandryjskiej.

W maju 1991 roku odbyła się konsekracja kościoła, poprzedzona misjami parafialnymi, które przeprowadzili OO. Redemptoryści z Warszawy.   
Proboszczem został ks. Jan Majewski,  który wcześniej był wikariuszem parafii św. Wojciecha w Nasielsku a potem administratorem tego ośrodka. Pracował między innymi: w Dobrzykowie, Baranowie, Krasnem, Bodzanowie, Nasielsku.

W roku 1997 wybudowano plebanię, którą poświęcił podczas wizytacji kanonicznej J.E. Ks. Biskup Zygmunt Kamiński.

W roku 2006 rozpoczęto budowę kościoła. Konsekracji kościoła dokonał 17 maja 2015 roku Ks. Biskup Piotr Libera.

W maju 2016 roku świętowaliśmy 25 lecie powstania parafii. Uroczystości przewodniczył Ks. Biskup Mirosław Milewski, biskup pomocniczy.