Parafia pod wezwaniem Narodzenia Najświętszej Marii Panny została erygowana w 1422 r. W tym to też okresie został wybudowany drewniany kościół z fundacji rycerza Janusza z Gościańczyc herbu Prus III. W XVI w. świątynia została rozebrana i jej miejsce została wzniesiona nowa, z cegły palonej przez rodzinę Mińskich. Pod koniec XVI w. wyniku pożaru, który wybuchł w mieście kościół spłonął.
Duży wpływ na odbudowę kościoła miał Stanisław Miński, który w dużej części sfinansował jego budowę, a po jego śmierci dzieła tego podjęła się jego rodzina. Udział w wzniesieniu świątyni miała także szlachta i mieszczaństwo. W 1629 r nastąpiła konsekracja kościoła przez sufragana i opata płockiego Stanisława Starczewskiego.
W 1807 r. świątynia została przebudowana ze stylu gotyckiego na styl klasycystyczny. W latach 1908-11 przechodzi kolejną przebudowę według projektu Józefa Dziekońskiego.
Na wyposażeniu kościoła znajduje się ołtarz główny z XVII w. krucyfiksem, który jest rzeźbiony w drewnie i dwa ołtarze boczne. Lewy z obrazem św. Antoniego Padewskiego autorstwa ks. Prałata Marcela Karpińskiego, jest obrazem ruchomy, który jest zmieniany obrazem „Jezu ufam Tobie”, namalowanym przez artystów malarzy z Krakowa – Ewę i Kazimierza Kawę. W prawym ołtarzu bocznym znajduje się obraz ukazujący wizerunek Matki Boskiej Anielskiej zwany także Matką Boską Mińską, który został namalowany na płótnie przez Jana Czesława Moniuszko w pierwszym dziesięcioleciu XX w.
Z historią tego obrazu jest związana postać generała Józefa Hallera, który to 12 sierpnia 1920 r. modlił się przed wizerunkiem Matki Boskiej Anielskiej wraz ze swym sztabę prosząc o zwycięstwo nad bolszewikami. W dniu 17 sierpnia 1920 r. dziękował za zwycięstwo i złożył prośbę o dalsze sukcesy armii polskiej.