Parafia w Stupsku należy do najstarszych ośrodków chrześcijaństwa na Mazowszu Północnym. Gród w Stupsku (Stołpsko) wspominany jest w tzw. falsyfikacie mogileńskim z ok. 1065 r., w którym mogła znajdować się kaplica grodowa. Po przeniesieniu Stupska na prawo chełmińskie, czyli przed 1384 r., wzniesiono nowy kościół parafialny, przy którym rezydował pierwszy znany z imienia pleban stupski, Bartłomiej, notowany w 1429 r. w kurendzie Jakuba Pszkowica. Prawdopodobnie ten kościół uległ zniszczeniu w 1494 r.
Kolejny kościół drewniany nosił wezwanie czczonego do dzisiaj w parafii św. Wojciecha, znajdowały się w nim cztery ołtarze i belka tęczowa. Brak na stałe rezydujących kapłanów w parafii i kolejne wojny spowodowały upadek budynku kościoła.
Staraniem cześnika ciechanowskiego Mikołaja Zielińskiego i jego żony Anny z Narzymskich odbudowano zniszczony kościół, który konsekrował 6 czerwca 1713 r. biskup płocki Ludwik Bartłomiej Załuski. Była to budowla drewniana, orientowana, o konstrukcji zrębowej, z zakrystią od północnej strony. Kościół miał trzy ołtarze, w głównym obraz Ukrzyżowania Jezusa. Nad kruchtą wzniesiono później dzwonnicę. W II połowie XVIII w. w Strzałkowie notowana była kaplica dworska, wystawiona w 1763 r. przez podkomorzynę płocką Katarzynę z Jaroszewskich Zielińską. W kolejnych latach parafią stupską zarządzali w różnych okresach także proboszczowie ze Żmijewa. W 1911 r. w wyniku ogromnego pożaru w Stupsku spłonął kościół z wyposażeniem. Dzięki ks. Janowi Dobeckiemu zakupiono drewnianą kaplicę z Sulerzyża, która od 1913 r. przez kolejnych pięćdziesiąt lat była miejscem modlitwy i sprawowania sakramentów.
Dopiero ks. proboszcz Marian Czapla podjął dzieło budowy nowej świątyni. Zaprojektował ją architekt Paweł Rzepecki, a została wzniesiona w latach 1958-1960. Nigdy jednak nie dokończono dwóch wież, zaprojektowanych na frontonie kościoła. Jest murowany, z czerwonej cegły. Kościół w stanie surowym poświęcił 6 listopada 1960 r. biskup sufragan Piotr Dudziec. W czasie, gdy proboszczem był ks. Ludwik Jasiński (1967-1982) w kościele wykonano sufit kasetonowy i nowy chór według projektu ks. Adama Skałbani SDB. W 1976 r. ufundowano 10-głosowe organy. Konsekracji dokonał 19 sierpnia 1978 r. biskup płocki Bogdan Marian Sikorski. Kolejni proboszczowie dopełniali dzieła wyposażenia wnętrza. Zakupiono ołtarz, chrzcielnicę, ławki i dzwony, wybudowany parkan wokół cmentarza przykościelnego. W czasie, gdy proboszczem był ks. Sławomir Obrębski, z pomocą parafian gruntownie odnowiono kościół i ołtarz, zostały także wymalowane nowe obrazy do wnętrza. W 1970 r. odlano trzy dzwony: „Wojciech”, „Józef” i „Stanisław Kostka” i zawieszono na jednej z wież kościoła. Barokowy ołtarz głównym z ok. 1700 r. z dawnej kaplicy: mensa z antepedium ze sceną Nawiedzenia NMP, obrazy św. Wojciecha, Matki Bożej Bolesnej i NMP z Dzieciątkiem. Chrzcielnica z drewna dębowego w formie kielicha z metalowym nakryciem.
Dekretem biskupa płockiego Bogdana Mariana Sikorskiego z dn. 19 czerwca 1971 r. wsie Młodynin Mały i Młodynin Duży odłączono od parafii Stupsk do parafii Żmijewo, zaś wieś Konopki-Janówek przyłączono z parafii Żmijewo do parafii Stupsk.
W 1996 r. z inicjatywy mieszkańców Konopek i ks. Mieczysława Białowąża urządzono prowizoryczną kaplicę, rozebraną w 2006 r. Na jej miejscu wzniesiono murowaną kaplicę filialną św. Krzysztofa, poświęconą 5 listopada 2009 r. przez biskupa płockiego Piotra Liberę.
Proboszcz