Parafię w Celestynowie erygowano dnia 13 sierpnia 1929 roku z części parafii Kołbiel, należącej wówczas do dekanatu praskiego. Nazwa miejscowości pochodzi od Celestyny, córki właściciela majątku Leopolda Polakiewicza.
Najstarszą osadą Celestynowa jest Radzin, który powstał w 1833, a jego właścicielem był Leopold Radziński. Miejscowość rozwinęła się w związku z budową kolei nadwiślańskiej, przyczynili się do tego także warszawiacy, którzy przyjeżdżali tu na letnisko. Duża odległość do kościoła w Kołbieli pozbawiała wczasowiczów i miejscową ludność łatwości pełnego uczestnictwa w życiu Kościoła. W 1927 przystąpiono do budowy drewnianej kaplicy, którą poświęcił 17 lipca tegoż roku Ks. Piotr Górski, proboszcz z Kołbieli. Pierwszym kapłanem, który przyjeżdżał do Celestynowa na niedziele i większe święta, był student z diecezji sandomierskiej, Ks. Stanisław Rostowski.
Kościół zbudowano w latach 1930-1932 z fundacji Edmunda Jankowskiego, profesora SGGW, organizatora szkoły ogrodniczej w Celestynowie, wielkiego społecznika odznaczonego medalem papieskim „Pro Ecclesia et Pontifice”. Projekt kościoła wykonał inż. arch. Tadeusz Szanjor. Kamień węgielny poświęcił Bp Stanisław Gall dnia 12 października 1930, a już w grudniu kościół zasklepiono i dach pokryto dachówką. Duszą poczynań w pierwszym okresie budowy był Ks. Anatol Sałaga, a od 3 lutego 1932 Ks. Jan Maciejewski. Bardzo wielu parafian pracowało bezinteresownie przy budowie. Świątynię poświęcił Bp Stanisław Gall dnia 30 października 1932, w uroczystość Chrystusa Króla. Ukoronowaniem budowy kościoła i stabilizacji życia parafialnego była konsekracja świątyni, której dokonał Bp Stanisław Gall w dniu 14 czerwca 1939. Lasy celestynowskie były miejscem wielu zwycięskich akcji Armii Krajowej. W pobliżu kościoła znajduje się pomnik w formie orła rozpiętego na krzyżu ku czci ofiar nalotu z 1 września 1939 i poległych w II wojnie światowej.
