Pierwsze pewne wiadomości źródłowe o Nawrze pochodzą z XIII w. Według dokumentu Heidenryka, biskupa chełmińskiego, wioska w 1248 r. stanowiła własność Fryderyka i Peregryna, rycerzy niemieckich, którzy otrzymali ją od zakonu krzyżackiego, władającego tym obszarem. W wyniku II pokoju toruńskiego (1466 r.) Nawra znalazła się w granicach państwa polskiego. Informacje o wsi i jej właścicielach z przełomu XV i XVI w. są bardzo skromne. Od 1652 r. przeszła ona w ręce Kruszyńskich, a od 1865 r., w związku z małżeństwem córki Władysława Kruszyńskiego, należała do rodu Sczanieckich aż do 1939 r.
Nawra była prawdopodobnie jednym z pierwszych ośrodków duszpasterskich erygowanej w 1243 r. diecezji chełmińskiej. Prawdopodobnie już w poł. XIII w. powołano tu do istnienia parafię, jednak pierwsza informacja o niej pochodzi dopiero z 1330 r. Pierwszy kościół w Nawrze, pw. św. Mateusza, został wzniesiony do końca XIII w. Był on usytuowany przy starym trakcie wiodącym z Torunia do Chełmna i Chełmży, w centrum wioski. Niestety, w 1618 r. kościół doszczętnie zniszczono. Na miejscu starej świątyni powstała nowa - pw. św. Katarzyny Aleksandryjskiej, konsekrowana prawdopodobnie w 1619 r. z okazji nadania odpustów dla kościoła przez nuncjusza apostolskiego F. Diotalleviego. W okresie wojen szwedzkich (1626-29) kościół ponownie został zniszczony. W jego odbudowę niemały wkład wniosła rodzina Kruszyńskich. To właśnie dzięki wspomnianej rodzinie świątynia nabrała stylu barokowego.
W I poł. XVII w. Kruszyńscy przyłączyli do swojej posiadłości część gruntów należących do kościoła. W rezultacie na uposażeniu parafii pozostała tylko nieznaczna część ziemi, która nie zapewniłaby nawet utrzymania miejscowemu proboszczowi. Wskutek tego kościół w Nawrze spełniał przez pewien czas tylko funkcję dworskiej kaplicy, gdyż nie było przy nim proboszcza, a Msze św. odprawiali kanonicy lub zakonnicy przybywający z Chełmży, Torunia lub Chełmna. Parafia odzyskała swe ziemie dopiero w II poł. XVIII w.
W latach 1778-86 Konstanty Kruszyński gruntownie odnowił świątynię. Szczególny rozkwit parafii obserwujemy w czasach, gdy majątek Nawra należał do rodziny Sczanieckich; wtedy parafia uaktywniła się na niwie naukowej, narodowej i gospodarczej. Dziś kościół jest otynkowany i otoczony starym drzewostanem.
Ciekawa jest historia obrazu przedstawiającego Madonnę trzymającą na lewej ręce Dzieciątko Jezus, a w prawej berło. Na głowach postaci znajdują się korony, a ponad nimi umieszczonych jest dwanaście gwiazd w półokręgu.
Historia wizerunku sięga czasów króla Zygmunta III Wazy i prowadzonej przez niego wojny z Moskwą w latach 1609-18, podczas której do niewoli dostał się dziedzic Nawry Bernard Kruszyński - sędzia ziemski chełmiński. Był on od dziecka gorącym czcicielem Najświętszej Panny, dlatego codziennie w czasie ciężkiej niewoli prosił Ją, aby go wybawiła z tego nieszczęścia. Ku swemu zdziwieniu pewnego dnia spostrzegł na zasuwie zamykającej komin obraz Najświętszej Bogarodzicy. Uszczęśliwiony tym niezwykłym zjawiskiem jeszcze bardziej modlił się do Niepokalanej Matki i wierzył, że zechce go wysłuchać. Sama niewola była już odtąd znośniejsza, ponieważ obraz stał się dla niego źródłem pociechy i ukojenia w cierpieniu. Wspominał potem, że wiele razy Matka Boża ukazywała mu się w śnie, pocieszała w cierpieniach, koiła jego bóle nadzieją rychłego wyzwolenia. Wreszcie, nie bez szczególnej łaski Najświętszej Panny, po 7 latach został uwolniony i powrócił do Ojczyzny. Opuszczając więzienie, nie mógł jednak rozstać się z ukochanym obrazem. Wyprosił go zatem dla siebie i umieścił w swoim pałacu. Matka Boża, ukazując mu się w śnie, napomniała, by oddał obraz do kościoła, gdzie możemy go oglądać po dziś dzień. W tym celu został on, prawdopodobnie dla umieszczenia we wspomnianym ołtarzu, przemalowany i obity rokokową i trybowaną sukienką. Wiadomość o nowym i „dziwnym” obrazie sprowadziła do Nawry licznych czcicieli Maryi.
W miejscowych aktach parafialnych zostało zapisanych wiele informacji o licznych uzdrowieniach i innych nadzwyczajnych łaskach doznanych w Nawrze za przyczyną Matki Bożej. Czytamy tam m. in., że pewna mieszczka z Torunia ciężko zachorowała w Nawrze podczas swojej podróży do Chełmna. Skoro tylko oddała się pod opiekę Najświętszej Matki przed Jej obrazem, jeszcze tej samej nocy wyzdrowiała i udała się w dalszą podróż.
Ks. Witkowski pisze o chorobie owczarza Wawrzyńca Rumatowskiego w 1767 r.: „A gdym go na śmierć dysponował, on skinął przy mnie na płaczącą żonę i te jej słowa szepnął: «Mam ufność w tutejszym obrazie Najświętszej Panny Maryi, że mnie przy życiu zachowa» i kazał mi dać przez żonę na pozłotę srebrnej sukienki obrazu 20 czerwonych złotych. Wkrótce potem wyzdrowiał”. Do dziś istnieje wygrawerowany na sukience znak cechu, rok tego złocenia - 1767 oraz imię i nazwisko złotnika - Jana Letyńskiego.
Nie brakowało również innych nadzwyczajnych znaków i zjawisk. Otóż przez 5 lat widywano czasami tak wielką światłość w kościele, że ludzie oblegali świątynię. Wspomniany proboszcz z Nawry pisał, że nieraz wstawał w nocy zbudzony tym faktem, gdyż zdawało mu się, że kościół płonie. Biegł w stronę świątyni, ale po wejściu do niej nie mógł się niczego doszukać. Zdarzenia te spowodowały, że rodzina Kruszyńskich złożyła ofiarę 1500 polskich złotych na wykonanie wiecznej lampy przed obraz Najświętszej Panienki.
W 1777 r., gdy przez nieostrożność pozostawiono palącą się świecę, w kościele wybuchł pożar, ogarniając cały ołtarz, tak że płomienie wydostawały się na zewnątrz. Obraz jednak nie uległ zniszczeniu, a ogień został z łatwością ugaszony kilkoma garściami śniegu i niewielką ilością wody.
Wszystkie cuda i łaski zwróciły uwagę władzy duchownej, dlatego na początku XIX stulecia biskup pomocniczy chełmiński Onufry Rogowski otrzymał polecenie od ówczesnego ordynariusza diecezji, aby pojechał do Nawry i zbadał mające tam miejsce cuda i znaki oraz odebrał pod przysięgą zeznania świadków. Niestety, utworzona komisja nie wydała oczekiwanych orzeczeń ze względu na ówczesne zamieszki wojenne.
Oprócz srebrnej sukienki, będącej także wotum wdzięczności, ludzie ofiarowali inne wota, które dzisiaj w liczbie około 60 znajdują się wokół obrazu. Te najstarsze, w kształcie plakietek, są zazwyczaj srebrne, trybowane i grawerowane. Jedno z nich, z widoczną rytowaną postacią wotantki klęczącej przed Matką Bożą z Dzieciątkiem, pochodzące z 1650 r., jest ufundowane przez żonę Bernarda Kruszyńskigo, Annę z Wedelstedtów.
Starsi mieszkańcy wspominają bardzo żywy kult przedwojennej społeczności nawrzańskiej, która nieustannie doznawała cudownej opieki Maryi. Jego potwierdzeniem jest przekaz ówczesnego proboszcza, ks. Franciszka Odrowskiego (1886 -1911), znajdujący się w miejscowych aktach parafialnych. Również z tamtego czasu zachowała się modlitwa:
Pomnij, o Panno święta, że nigdy nie słyszano, abyśmy, gdy się w potrzebie pod Twoją opiekę uciekali, Twego wspomożenia błagali, od Ciebie opuszczeni byli.
Takąż ożywieni ufnością, o cudowna Panno Nawrzyńska, Naród Polski do stóp Twoich przypada i błagalne wznosi ku Tobie wołanie. Szafarko Łask Bożych, Pani Nawrzyńska, Królestwa Swego strzeż! Na straży granic Polski, o Pani nasza stań! Płaszczem swym, jako puklerzem od wrogów chroń! Wojnom, zarazom, niezgodzie i klęskom wszelkim przystępu do Polski broń! A dusze Narodu Twego do Syna Swego skłoń.
O Matko Chrystusowa, Matko Łaski Bożej, Najświętsza Panno w obrazie nawrzyńskim, nie gardź tym Polski wołaniem, lecz usłysz je i racz wysłuchać o łaskawa, o litościwa Pani i Królowo nasza.

Opis dziejów sanktuarium w Nawrze pochodzi z książki: Sanktuaria maryjne diecezji toruńskiej, wydanej w 2003 r. przez Toruńskie Wydawnictwo Diecezjalne. Książka jest do nabycia m.in. w Księgarni Diecezjalnej w Toruniu oraz w siedzibie Wydawnictwa przy ul. Łaziennej 18 w Toruniu.