Parafia pw. Narodzenia NMP została erygowana w 1409 r. z fundacji księcia mazowieckiego Janusza. Pierwotne terytorium obejmowało obecne parafie: Dobrylas, Kuzie, Miastkowo, Zbójna i częściowo Turośl.
Parafia Nowogród utworzona została przez biskupa płockiego Jakuba Kurdwanowskiego w roku 1409 z fundacji księcia mazowieckiego Janusza Starszego. Przeznaczył na ten cel 2 włóki chełmińskie ziemi. W roku 1434 wnuk księcia Janusza Bolesław dołożył jeszcze jedną włókę. (1 włóka chełmińska (staropolska) = 30 mórg = 17,955 ha) Teren parafii (wraz z całym Mazowszem) aż do roku 1526 był własnością Książąt Ma zowieckich, kiedy to Księżna Anna zrzekła się Księstwa Mazowieckiego na korzyść króla Zygmunta Starego.
Jeszcze w roku 1578 wymienia się jako należące do parafii tylko wioski po lewej stronie rzeki Narew, ponieważ tereny po stronie prawej nie były zamieszkałe. Stałe osiedla po prawej stronie rzeki, na terenach zwanych Puszczą Nowogrodzką, która łączyła się dalej z Puszczą Myszyniecką, zaczęły powstawać w wieku XVII, a zwłaszcza w XVIII i XIX. Wioski te, w miarę powstawania przyłączane były do parafii Nowogród. Rozwój ich był tak intensywny, że wg spisu z roku 1860 większość wiosek i terenu parafii leżało już po prawej stronie rzeki Narew. Parafia wówczas była li czebnie jedną z większych a nawet największą (jak podaje ks. Witold Jemielity) w całej Diecezji Sejneńskiej i liczyła 10390 parafian (rok 1891).
Wtedy to, z racji tak dużej liczby parafian oraz braku stałej przeprawy przez rzekę na skutek zniszczonych mostów, dokonano podziału parafii, tworząc nową parafię w miejscowości Zbójna. Przy Nowogrodzie pozo stało wówczas 3501 parafian. W następnych latach ze Zbójnej wyodrębniono jeszcze dwie kolejne parafie. Tak więc parafia Nowogród jest „matką” parafii Zbójna, Dobrylas i Kuzie.
Pierwszy kościół w Nowogrodzie istniał na krótko przed 1396 r., zanim powstała parafia. O tym lub kolejnym drewnianym kościele jest wzmianka z 1565 r. Następny kościół, już murowany został wzniesiony po roku 1615. Wieży nie było, w ścianach od wewnątrz były w górze okna, u dołu nisze do obrazów i figur, w ołtarzu głównym obraz MB Pocieszenia. Sam kościół był znacznie niższy i mniejszy od dzisiejszego, w dolnej części muru sterczały wielkie kamienie. Ten mocno ucierpiał w czasie najazdu szwedzkiego (1655-1660).
Kiedy uległ całkowitemu zniszczeniu w 1778 r., pobudowano prowi zoryczną drewnianą świątynię, zaczęto równocześnie budowę na starym miejscu nowego kościoła, który wykończono w 1815 r. Miał kształt krzyża, pokryty dachówką, pułap z desek podparty na belkach 8 drewnianymi słupami. W parafii wtedy było 3 księży. Kościół ten konsekrował biskup Czyżewski 1 września 1821 r.
W roku 1865 kościół rozbudowano. Dobudowano wtedy 2 nawy bocz ne. Dobudowano też o 14 łokci (ok. 8 m) prezbiterium i murowaną zakrystię (po zachodniej stronie), poprzednia była drewniana. Cały kościół podniesiono wtedy o parę łokci w górę, bo był za niski. Proboszczem był wtedy ks. Romuald Skrodzki. Kościół tak zmodernizowany konsekrował w 1870 r. bp Wierzbowski. Kościół prezentował się okazale, kryty blachą, pobielony na zewnątrz widziany był z daleka.
Kiedy sprawiono nowe organy (1890), chór okazał się za mały, rozbudowano kościół od strony wejścia, prawdopodobnie wtedy dobudowano wieżę.
Kościół ten przetrwał do 1914 r. Nadwerężony pociskami dział niemieckich, wysadzony i podpalony przez wojska rosyjskie. W 1917 urządzono tymczasowy kościół, odbudowę zaczęto w 1922. Ukończono na jesieni 1926 r. Podwyższono go znów przy tej okazji o kilka metrów, pokryto dachówką, odbudowano wieżę. Wtedy też powstała obecna zakrystia. Dnia 12 grudnia 1926 r. uroczystego poświęcenia kościoła dokonał biskup Stanisław Łukomski.
W czasie drugiej wojny światowej kościół został zbombardowany, spalony i zburzony. Po wojnie przystąpiono do odbudowy, którą ukończono w 1956 r. Wieżę odbudowano w roku 1982.
Obecny kościół jest z cegły, trójnawowy, tynkowany, o wymiarach: długość 42 m, szerokość 25 m, wysokość do sklepienia 12,5 m, wieża 38 m. Najstarszą częścią kościoła jest część obecnego prezbiterium. W kościele są trzy drewniane ołtarze. W głównym (w formie tryptyku) znajdują się figury Chrystusa Ukrzyżowanego, Matki Boskiej i św. Jana. Po bokach płaskorzeźby przedstawiające tajemnice różańcowe. W ołtarzach bocznych umieszczono obrazy św. Rocha i Serca Pana Jezusa. Wszystkie ołtarze są współczesne, z lat 80. XX w.
Cmentarz parafialny został założony w roku 1815, otoczony murem kamiennym. Powiększenia cmentarza dokonano dwukrotnie: w roku 1861 oraz w latach 80. XX w.
Plebania zbudowana w roku 1882, wpisana jest do rejestru zabytków. Obecnie nie używana. Rolę plebanii spełnia Dom Parafialny, wybudowa ny w roku 1988.

Liczba wiernych: 3140