Świątynia została ufundowana podczas lokacji miasta na prawie magdeburskim w 1346 roku przez króla Kazimierza Wielkiego.
Stosowny napis potwierdzający to zdarzenie został umieszczony wewnątrz kościoła i głosi: Fundata a Casimiro Magno Anno Domini 1346.
Powstało w tym czasie tylko murowane prezbiterium, które zachowało się do dnia dzisiejszego, natomiast pozostała cześć świątyni była drewniana. Z czasów budowy zachowały się również kamienne kropielnice umieszczone przy wejściach.
Liczne pożary które nawiedzały Nowy Targ, jak również najazd wojsk szwedzkich zniszczyły świątynię. Po kolejnym pożarze w 1601 r., podjęto decyzję o odbudowie świątyni w formie murowanej. Świątynię odbudowano w latach 1606 - 1655. Wzniesiono wówczas murowaną nawę oraz wieżę, pokrytą, barokowym hełmem W 1634 roku mieszczanie nowotarscy dobudowali do kościoła kaplicę NMP Różańcowej, zaś w roku 1717 kaplica ta uzyskała własnego kapłana oraz naczynia i szaty liturgiczne.
Wyposażenie wnętrza pochodzi głównie z czasów baroku, ale szczególną uwagę należy zwrócić na znajdujący się w prezbiterium nad wejściem do zakrystii obraz „Matki Boskiej z gruszką”.
Pierwotnie obraz Matki Boskiej z Dzieciątkiem znajdował się w drewnianej świątyni pod wezwaniem świętej Anny, ale ze względów bezpieczeństwa został przeniesiony. Obraz powstał zapewne w XV wieku i reprezentuje tzw. szkołę małopolską.