Gietrzwałd lokowany został na prawie chełmińskim 19 maja 1352 roku. Akt lokacyjny wydała Warmińska Kapituła Katedralna, a pierwotna niemiecka nazwa to Dietrichswalde od zasadzcy wsi sołtysa Dittricha. Pierwsze wzmianki o parafii pochodzą z drugiej połowy XIV w., związane jest to z postawieniem niewielkiej drewnianej kaplicy. Podczas wojny polsko-krzyżackiej kaplica i wieś zostały zniszczone, wybudowano więc jednonawowy, gotycki kościół na podmurówce z kamienia, znacznie większy od pierwotnej świątyni. 31 marca 1500 r. został konsekrowany przez biskupa warmińskiego Jana Wilde i poświęcony ku czci Narodzenia Najświętszej Panny Marii. Kościół był wielokrotnie przebudowywany, dostosowywano go do panujących stylów architektonicznych. Najpierw do renesansu pod koniec XVI w., a w okresie baroku wyposażono go w nowe ołtarze.
W 1790 r. biskup Ignacy Krasicki dodał do świątyni dwa nowe wezwania: św. Jana Ewangelisty i św. Apostołów Piotra I Pawła. W latach 1866-1869 ówczesny proboszcz dokonał kolejnej przebudowy a właściwie kapitalnego remontu; wzmocniono fundamenty i ściany dobudowywując 6 zewnętrznych przypór, rozebrano również dwie stare kruchty i przykościelną kostnicę. Wkrótce jednak okazało się, że świątynia wymaga kolejnych przeróbek, a przede wszystkim powiększenia swych rozmiarów. Objawienia w 1877 r. sprawiły, że do Gietrzwałdu zaczęły napływać niezliczone rzesze pielgrzymów. Remont rozpoczęto w 1878 r a zakończono w roku 1884. Pod ścisłym nadzorem architekta Arnolda Güldenpfenninga dobudowano poprzeczną nawę z emporami, prezbiterium z kryptą oraz transept z chórem. Kościół otrzymał w ten sposób kształt krzyża rzymskiego, ale stracił swój pierwotny układ salowy. W tym okresie rozebrano tez drewnianą wieżę zastępując murowaną z cegły z neogotyckim zakończeniem.
Jako że świątynia usytuowana jest na wzniesieniu, wieża widoczna jest ze znacznej odległości. Dodatkowe uroku daje główne wejście, podkreślone układem ciągu schodów otoczonych szpalerem starych lip. Wyposażenie wnętrza świątyni jest głównie neogotyckie, szczególnej uwagi zasługuje ołtarz główny, piękna polichromia, drewniana Pieta z 1425 r., liczne rzeźby i obrazy. Najważniejszy to ten umieszczony w ołtarzu głównym, pochodzący z poł. XVI w. obraz Matki Boskiej z Dzieciątkiem. Kościół jest centralną częścią Sanktuarium Maryjnego, nazywanego też Częstochową Północy lub Polskim Lourdes, świadczą o tym nie kończące się pielgrzymki wiernych nie zależnie od pory roku. Dnia 2 lutego 1970 r. bullą papieża Pawła VI podniesiono kościół do rangi bazyliki mniejszej.