Do 1978 r. w Ostrołęce była jedna parafia przy kościele pw. Nawiedzenia NMP erygowana w 1399 r. z fundacji księcia Mazowieckiego Janusza. Dnia 1.09.1978 r. z terytorium parafii Nawiedzenia NMP powstała w Ostrołęce przy kościele poklasztornym parafia pw. św. Antoniego Padewskiego. Następnie we wsiach należących do parafii farnej, z jej terytorium, powstały nowe parafie: w 1987 r. Obierwia, w 1992 r. Łęg Starościński i w 1993 r. Olszewo-Borki. Ponadto niektóre wioski z parafii farnej zostały przyłączone do nowopowstających sąsiednich parafii.

Historia parafii Ostrołęka sięga co najmniej XIV wieku, choć nie zachowały się dokumenty potwierdzające dokładną datę jej powstania. Wspomniana parafia jest związana z kościołem, który początkowo był pod wezwaniem św. Mikołaja – patrona żeglarzy i kupców, co miało związek z gospodarczo strategiczną lokalizacją Ostrołęki nad Narwią, w rejonie szlaków handlowych.

Parafia ostrołęcka, według dostępnych źródeł, została utworzona na przełomie XIV i XV wieku. Chociaż nie ma dokumentu erekcyjnego, to wiadomo, że w 1399 roku książę Janusz I nadał kościołowi w Ostrołęce ziemię, co mogło stanowić jeden z pierwszych kroków w kierunku formalizacji tej parafii. W wyniku tego nadania kościół stał się siedzibą parafii, która obejmowała nie tylko Ostrołękę, ale i okolice. Z biegiem lat parafia ostrołęcka powiększała się, a z czasem przekształciła w ważne centrum religijne w regionie. W XVI wieku, konkretnie w roku 1530, parafia ostrołęcka znajdowała się w dekanacie łomżyńskim, który należał do archidiakonatu pułtuskiego.

W XVII wieku, szczególnie po najazdach szwedzkich (1656–1660), liczba mieszkańców parafii zmniejszyła się znacznie, a miejscowości parafialne zostały zniszczone. W wyniku wojen i epidemii niektóre miejscowości zostały całkowicie opustoszałe. W 1676–1677, mimo tych trudności, w parafii wciąż istniały miejscowości, które płaciły pogłówne, w tym Ostrołęka, Łączki, Grabowo, Kruki i inne.

Obecny kościół murowany w stylu barokowym pw. Nawiedzenia NMP zbudowany w latach 1647-1660 staraniem ks. Mateusza Niskiego i ks. Stanisława Kostki Zacharkiewicza. Konsekrowany 14.02.1696 r. przez Biskupa płockiego Andrzeja Chryzostoma Załuskiego; powtórnie konsekrowany 7.03.1773 r. przez Biskupa kujawskiego Jana Dembowskiego z upoważnienia Biskupa płockiego Antoniego Szeptyckiego. W 1938 r. rozpoczęto rozbudowę i powiększanie kościoła staraniem ks. E. Waltera.

W czasie II wojny światowej, w 1944 roku, kościół Nawiedzenia NMP w Ostrołęce doznał poważnych zniszczeń. Podczas okupacji niemieckiej Ostrołęka była miejscem intensywnych walk, a miasto zostało częściowo zniszczone. Kościół, będący centrum religijnym parafii, ucierpiał w wyniku działań wojennych, jednak po zakończeniu wojny przystąpiono do jego odbudowy.

Kościół został odbudowany dzięki staraniom proboszcza ks. Bronisława Tałandzewicza, który zorganizował środki i nadzorował prace odbudowy. Po zakończeniu prac restauracyjnych kościół został rekonsekrowany 23 maja 1955 roku przez biskupa pomocniczego Aleksandra Mościckiego. Rekonsekracja stanowiła symboliczne przywrócenie świątyni do pełnej funkcji sakralnej, a także była ważnym momentem duchowym dla wiernych, którzy doświadczyli tragedii wojennej.

Plebania murowana, wybudowana ok. 1900 r. staraniem ks. prob. Kajetana Śmiechowskiego; wpisana do rejestru zabytków.

Liczba wiernych: 10 000