Historia parafii
W średniowieczu kościoły stawiano na miejscach dawnych pogańskich kultów. Tak stało się i w naszych przypadku, o czym świadczą odnajdywane na terenie, gdzie stoi plebania, pozostałości po cmentarzu pogańskim. „W ogrodzie plebanii znaleziono (około 20 lat temu [tzn. ok. 1879r. – przyp. P.S.]) kilka grobów murowanych z cegły, sklepionych, w których były popielnice. Użyto ich do wysypania i wyrównania drogi.” („Przegląd katolicki. Rok 1865”) Inną wersję tego wydarzenia przedstawiał Józef Sienicki z Zagwizd, wieloletni członek Dozoru Kościelnego, we wspomnieniach spisanych przez Marię Zalewską. Mówił, że pięć masywnych urn wydobyto podczas prac przy robieniu regulówki pod wino. W urnach znajdował się nie tylko popiół, ale i „całe szczęki z białymi, zdrowymi zębami„. Ówczesny proboszcz, ks. Aleksander Kamiński, nie powiadomił o tym Towarzystwa Archeologicznego, ale „z wielką czcią pochował je na cmentarzu grzebalnym”. Parafia erygowana została w 1388r. przez bp. Ścibora. Do parafii należały wówczas wsie: Biskupice, Czarnoty, Latonice, Miszewo i Łuszczewo. Na początku stała tu świątynia drewniana. Wznoszenie obecnie stojącego kościoła rozpoczęto za czasów księżnej Anny mazowieckiej w XV w.
Budowę kościoła zakończono za czasów synowej księżnej Anny – księżnej Barbary w 1471r. Drewniany kościół rozebrano i postawiono w innym miejscu. Od tego momentu w Nowym Mieście znajdowały się 2 parafie. Parafie te otrzymały patronki swych fundatorek – obecna św. Anny (poprzednia miała za patronów Matkę Boską i Wszystkich Świętych), nowa szpitalna z kaplicą (lub małym kościołem) św. Barbary. W podziemiach nowomiejskiego kościoła spoczęła na wieki księżna Barbara. Po wielu latach, bo dopiero w roku 2014, doczekała się płyty nagrobnej. Przy szpitalu znajdowały się też kaplice św. Leonarda i św. Ducha. Szpital jak i kościół św. Barbary spłonął podczas potopu szwedzkiego. W latach 1693-1818 funkcjonował dekanat nowomiejski, do którego należały następujące parafie: Cieksyn, Ciemniewko, Gromadzyn (dziś nie istniejąca), Klukowo, Kraszewo, Królewo, Łopacin, Nasielsk, Nowe Miasto, Sochocin i Sońsk. Podczas wojen napoleońskich w Nowym Mieście stacjonowało wojsko francuskie. Swoją siedzibę miało w kościele. Józef Sieniecki wspominał, że żołnierze zdewastowali kościół, przez co świątynia przez dłuższy czas była nieczynna
W XIX zaczął funkcjonować cmentarz grzebalny w odległości ok. 350 m od kościoła. Wcześniej zmarłych chowano na cmentarzu w obrębie kościoła lub w podziemnych kryptach. Pochówków tam było bardzo dużo, o czym świadczą zapisy w księgach metrykalnych „sepulta in ecclesia”, niektóre metryki dokładnie precyzowały miejsce np. „pod krzyżem”, „pod chórem” czy też w kaplicy Miszewskiej (kaplicy południowej), którą można by nazwać miejscem pochówku szczególnie zasłużonych (nie tylko dziedziców z Miszewa).
W 1865r. parafię wizytował bp Wincenty Popiel. Relacja ukazała się „Przeglądzie Katolickim”:
„…udał się ks. biskup do Nowego-Miasta. Po wprowadzeniu solennem do kościoła, i stosownem przemówieniu przez ks. proboszcza Kamińskiego, JE ks. poświęcił długi czas obejrzeniu znakomitości tego kościoła, a mianowicie wielkiego ołtarza, który jest arcydziełem sztuki. Ma on wielkie podobieństwo do wielkiego ołtarza w kościele metropolitarnym świętego Jana w Warszawie, z tą różnicą, że nie na dwie, ale na trzy kondygnacje się wznosi. Głównym obrazem w tym ołtarzu jest Matka Boska z dziecięciem Jezus na ręku. Obok tego obrazu w małym niszach są umieszczone małe aniołki, a po za niemi dwie duże figury Apostołów. W środku drugiego piętra jest obraz świętej Trójcy pięknego pędzla, a obok niego stoją figury świętych Wojciecha i Stanisława, które odpowiadają statuom apostołów pierwszego piętra. Trzecia kondygnacja, podobnież jest urządzona, tylko w mniejszych rozmiarach, lecz znaczenia obrazu i towarzyszących tymuż figur rzeźbionych trudno odgadnąć. Cały ten ołtarz, pierwotnie był pozłocony, twarze tylko figur były malowane kolorami, dzisiaj został odmalowany farbą koloru brązowego. (…) Opuścił ks. biskup Nowe-Miasto z prawdziwą satysfakcją i zadowoleniem duszy.” W 1891 odbyła się wizytacja dziekańska. W protokole czytamy: „Przechodził kościół ten różne koleje losu, bywał niejednokrotnie zupełnie zdezelowany, do chwały Bożej niezdatny i zapieczętowany; kilkakrotnie był restaurowany jako to w r. 1822, 1846 1847, w 1862 i ostatecznie w 1886 i 1887, za obecnej administracji tą parafią i kościołem X. I. Radzymiński, ale przy każdej z powyższych restauracji, wykończonym z braku odpowiednich funduszy nie został.” Cyt. za: „Korespondencja Przeglądu Katolickiego”, Pułtusk, 16 czerwca 1865 [w: „Przegląd katolicki. Rok 1865”, druk J. Krokoszyńskiego, Warszawa 1865]