W 1998 r. Nowogródek Pomorski obchodził 700-lecie udokumentowanego istnienia. Dziś leży trochę na uboczu głównych dróg, ale przed wiekami był dobrze prosperującym miasteczkiem. Świadczy o tym układ ulic rozchodzących się promieniście od niedużego ryneczku.
Pierwsi osiedli tu Łużyczanie (potwierdzają to badania archeologiczne), później gród był własnością templariuszy, wreszcie margrabiów brandenburskich. Jedna z legend głosi, że nazwę swą zawdzięcza właśnie rycerzom zakonnym, którzy, na przekór staremu grodowi, wznieśli na Wzgórzu Klasztornym nowy zamek, czyli „Nowogródek”. Prywatne miasteczko, będące przez lata własnością różnych rodów rycerskich, rozwijało się pomyślnie aż do wojny trzydziestoletniej (1618-48). Po jej zakończeniu wskutek znacznych zniszczeń zdegradowano je do roli wsi - i tak już pozostało.
Pierwszy solidny kościół powstał tu już w drugiej połowie XIII w. Wzniesiono go z ciosów granitowych na niewielkim wyniesieniu terenu. W XVII w. uległ zniszczeniu (wraz z całym miasteczkiem). Odbudowano go dopiero po 100 latach – w 1752 r. – używając do tego granitowej kostki pochodzącej ze zrujnowanej, wcześniejszej świątyni. Z tego też okresu pochodzi drewniana wieża z barokowym hełmem. Murowane kruchty są XIX-wieczne. W 1947 r. przystosowano go do potrzeb katolików, od 1948 r. funkcjonuje tu samodzielna parafia. Świątynia nosi dziś wezwanie MB Królowej Polski. Wewnątrz zachowała się ludowa polichromia barokowa z XVIII w. i neobarokowy ołtarz z XIX w. Także neobarokowe organy Sauera z przełomu XIX i XX w. - staraniem proboszcza i parafian - odrestaurowano w 2007 r. Kościół wpisano do rejestru zabytków w 1956 r. pod nr 138.