Parafię erygował Kard. Aleksander Kakowski 1 kwietnia 1924 roku wydzielając ją z parafii Świętej Trójcy w Kobyłce. W XV w. była to drobno-szlachecka wieś o nazwie Wolumino. W 1825 r. miała zaledwie 90 mieszkańców; rozwinęła się dzięki linii kolejowej poprowadzonej w 1862 r.. Prawa miejskie Wołomin otrzymał 4 lutego 1919 r. Wierni w 1902 roku wybudowali tu małą kapliczkę istniejącą, obok kościoła, do dnia dzisiejszego (mieści się w niej magazyn odzieży Caritas dla ubogich). Plac pod budowę kościoła poświęcił 24 listopada 1906 roku Ks. Franciszek-Ksawery Marmo, proboszcz z Kobyłki. Budowę kaplicy (tak nazywano świątynię, gdyż na budowę kościoła trzeba było mieć zgodę cara z Petersburga) rozpoczęli sami mieszkańcy w 1908 r. w stylu neogotyckim (projektant jest nieznany).

Świątynia w stanie surowym, pokryta dachówką, była gotowa w 1914 r. Wojna przerwała dalszą budowę. Mszę Św. zaczęto odprawiać w 1920 r. Pierwszy proboszcz, Ks. Jan Golędzinowski duszpasterzował w Wołominie do 1932 r. (odszedł do budowy kościoła Chrystusa Króla w Warszawie-Targówku): ukończył kościół o powierzchni 200 m2, wstawił trzy ołtarze, organy i ławki, ułożył posadzkę z terakoty; zbudował także plebanię. Podczas pierwszej wizytacji kanonicznej, 27 sierpnia 1927 roku, Kard. Aleksander Kakowski konsekrował kościół.

Podczas walk o Wołomin w sierpniu 1944 roku wojska rosyjskie zniszczyły połowę wieży; resztę wysadzili Niemcy 5 września 1944 roku: ciężar cegieł zniszczył prawie cały kościół: ocalało tylko prezbiterium i ołtarze. Ks. Apoloniusz Kosiński zbudował tymczasową kaplicę, którą w październiku 1946 r. poświęcił Kard. August Hlond. Kolejny proboszcz, Ks. kan. Walenty Zasada (więzień Dachau), zbudował 10-głosowe organy w kaplicy grające do dnia dzisiejszego. Dopiero Ks. Mieczysław Grabowski w latach 1950-1953 wybudował obecny kościół, dwukrotnie większy od zburzonego przez Niemców. Z dawnego kościoła pozostało prezbiterium i trzy ołtarze. Autorem projektu był prof. Stanisław Marzyński.

Początkowo miał poświęcić kościół Kard. Stefan Wyszyński w dniu 26 sierpnia 1953 roku, ale przełożył uroczystość na 11 października; po aresztowaniu w dniu 25 września nie mógł przybyć, więc uczynił to Bp Wacław Majewski. Kolejny proboszcz, Ks. prał. Jan Sikora, dobudował dwie wieże, położył elewację zewnętrzną i umeblował kościół. Uroczystości konsekracyjnej w dniu 6 października 1966 roku przewodniczył Prymas Stefan Wyszyński. Dzięki staraniom Ks. prał. Jana Sikory powstały trzy nowe parafie: Św. Józefa Robotnika, MB Królowej Polski i NMP Królowej Różańca Św. w Majdanie. Przy kościele znajduje się grota z figurą MB z Lourdes zbudowana przez Ks. Mieczysława Grabowskiego w setną rocznicę objawień w Lourdes. W 2005 r. został wybudowany pomnik ofiar Katynia, który poświęcił Bp Stanisław Kędziora. W 2008 r. Bp Kazimierz Romaniuk poświęcił pomnik Prymasa Tysiąclecia, Kard. Stefana Wyszyńskiego.