Wieś Leszczydół Nowiny od początków swojego istnienia należała do parafii Św. Idziego w Wyszkowie. W drugiej połowie lat 90-tych XX wieku, wśród mieszkańców zrodziła się idea budowy własnej świątyni. W roku 1997 grupa mieszkańców, wraz z ówczesnym proboszczem parafii Św. Idziego księdzem dziekanem Wojciechem Borkowskim przedstawiła swoją prośbę biskupowi Stanisławowi Stefankowi.
Po zaakceptowaniu przez biskupa idei budowy świątyni, zostały zakupione z funduszu diecezjalnego przez księdza proboszcza dwie działki o łącznej powierzchni 0,6 h.
Pierwsze nabożeństwa odprawiane zostało w październiku 1998 roku w sali gimnastycznej tutejszej szkoły przez księdza Tadeusza Masłowskiego, wikariusza Parafii św. Idziego w Wyszkowie. Następnie raz w miesiącu o godz. 14.00 odprawiana była niedzielna Msza Św. W przygotowaniach do tego wydarzenia czynnie uczestniczyli mieszkańcy wsi, sprawując posługę lektorską lub śpiewanie psalmów.
W 1999 roku zostaje powołany i zarejestrowany w Urzędzie Gminy Wyszków Społeczny Komitet Budowy Kościoła. Przewodniczącym zostaje ks. Tadeusz Masłowski, Zastępcą p. Zbigniew Ciarkowski, Skarbnikiem p. Henryk Książek a sekretarzem p. Elżbieta Baranowska. Członkowie komitetu podjęli się również comiesięcznych zbiórek ofiar na budowę świątyni. W międzyczasie powołana zostaje przez ks. Tadeusza Masłowskiego grupa ministrantów. Święta takie jak, poświęcenie pól mają teraz szczególną, historyczną oprawę. Przejazdy pomiędzy kapliczkami odbywają się wozami konnymi i w asyście grupy rekonstrukcyjnej kawalerii. Od 1999 roku trwały również prace nad projektem kościoła, które prowadził architekt z Łomży p. Jerzy Minkowski.
W 2000 roku na terenie działki parafialnej postawiony został krzyż a 14.06.2000 roku Ks. Biskup Stanisław Stefanek dokonał jego poświęcenia. W roku tym wydane zostało również pozwolenie na budowę. W dniu 29 października tegoż roku ustanowiony został rektorat p.w. Chrystusa Sługi, dzięki czemu ks. Tadeusz Masłowski mógł zorganizować dla parafian Mszę św. odprawianą w każdą niedzielę i święta na sali gimnastycznej.
Pierwsze prace budowlane rozpoczęły się w marcu 2001 roku. Prowadził je p. R. Aksamitowski. W tym samym roku zamontowany też został na prowizorycznej podstawie dzwon ufundowany przez ks. Henryka Kietlińskiego i ks. Jerzego Błaszczaka. W listopadzie tegoż roku odprawiona została pierwsza Msza św. w kaplicy, która urządzona została w podziemiach budynku, którą w dniu 1 grudnia poświęcił ks. Biskup Stanisław Stefanek.
Na wiosnę 2002 roku wznowione zostały prace budowlane a kolejnym budowniczym kościoła został p. Waldemar Brzostek z Ostrowi Mazowieckiej. W tym roku zostały dokończone prace wykończeniowe pomieszczeń przy kaplicznych, w których następnie urządzona została plebania.
W dniu 5 maja w kaplicy została zamontowana i poświęcona tablica pamiątkowa ku czci żołnierzy AK, zamordowanych przez hitlerowców po pacyfikacjach jakie miały miejsce w Leszczydole w maju 1944 roku. Tablica ufundowana została przez rodziny pomordowanych żołnierzy.
Po długiej zimie 2002/2003 rozpoczęto kolejny etap prac nad budową świątyni. 7 czerwca 2003 ks. Biskup Stanisław Stefanek poświęcił kamień węgielny, który następnie wmurowane w ścianę frontową kościoła. Kamień ten pochodzi z Izraela z Góry Oliwnej i posiada certyfikat autentyczności. Przywieziony został przez p. Andrzeja Sawickiego w 2002 roku. We wrześniu tegoż roku zakończone zostały prace budowlane.
W trakcie kolędy 2003 roku ksiądz proboszcz policzył wszystkich parafian. W roku tym było ich 1131 osób.
W roku 2004 plan budowy przewidywał dokończenie budowy wieży kościoła, którą szczęśliwie zakończono montażem krzyża na jej szczycie oraz instalacją dzwonu, który od tej chwili słyszany był w całej parafii. W roku tym zostało również wykonane pokrycie dachowe z blachy miedzianej.
Kolejne lata budowy kościoła skupiały się na gromadzeniu funduszy i spłaty dotychczasowych zobowiązań finansowych. Źródłami tymi były głównie co miesięczne datki składane przez parafian, ofiary zbierane w innych parafiach, gdzie ksiądz proboszcz Tadeusz Masłowski głosił Słowo Boże oraz indywidualnych ofiar składanych przez ludzi i instytucje.
W sierpniu 2011 roku posługę w parafii leszczydolskiej kończy dotychczasowy proboszcz, którego ksiądz Biskup przenosi do parafii Lipniki. Na jego miejsce wyznaczony został nowy proboszcz ks. Jan Soliwoda, która rozpoczyna swoją posługę w dniu 17.08.2011
Ksiądz Jan intensywnie kontynuuje dzieło poprzednika. Dobudowana zostaje część kaplicy z prezbiterium a całość zostaje zadaszona. W latach 2012-2014 trwa wykończenie wnętrza świątyni. Położone zostają tynki, wymalowane ściany oraz elewacja świątyni.
W roku 2014 dokonuje się oficjalne przeniesienie sprawowania Eucharystii do wnętrza kościoła.
W 2015 roku teren zostaje ogrodzony oraz wyznaczone zostaje nowe miejsce do parkowania pojazdów.
Nasza świątynia jest piękniejsza każdego roku.