Parafia powstała prawdopodobnie w 1300 roku. Pierwsze wzmianki o niej pochodzą z lat 1402-1416 i 1445. W obrębie parafii znajdowała się kaplica, która była zlokalizowana na dziedzińcu nieistniejącego dzisiaj zamku krzyżackiego w miejscowości Wieldządz. Parafia ta jest dedykowana Świętemu Janowi Chrzcicielowi i nosi to wezwanie od 1647 roku lub nawet wcześniej. Budowa kościoła rozpoczęła się po roku 1289, co było wynikiem nadania ziemi chełmińskiej przez komtura. Prace nad kościołem zakończono w pierwszej połowie XIV wieku. Niestety, w czasie wojen szwedzkich kościół został znacznie zniszczony. Dopiero w 1908 roku przeprowadzono jego renowację, w ramach której wnętrze zostało ozdobione polichromią autorstwa Fehlberga z Berlina. Wtedy także pierwotną murowaną iglicę wieży zastąpiono dachem namiotowym, który pokryty jest dachówką.
Kościół znajduje się w centrum miejscowości Nowa Wieś Królewska, na niewielkim wzniesieniu, przy drodze Uciąż - Wieldządz, na północ od głównej drogi prowadzącej z Wąbrzeźna do Chełmna. Otoczony jest kamiennym murem i na jego terenie znajduje się parafialny cmentarz. Poza ogrodzeniem, od strony północnej, znajduje się drugi cmentarz parafialny.
Kościół został wzniesiony na fundamentach z kamienia polnego. Ściany nawy oraz dolne części prezbiterium i wieży zbudowano również z kamienia polnego. Reszta kościoła została wykonana z cegły zendrówki. Części takie jak zakrystia, boczna kruchta, blendy, fryzy, oraz okna są pokryte tynkiem. Ściany prezbiterium ozdobione są ceramicznym fryzem arkadkowym, a portale są bogato zdobione w formie uskoków. Wnętrze budynku jest ozdobione różnymi rodzajami sufitów i stropów. Na przykład, kruchta ma strop w kolebkowy z ozdobnymi lunetami, a w zakrystii i wejściowej kruchcie jest płaski sufit. Wieża ma stropy na pierwszym i drugim piętrze, które są wsparte na belkach. Drewniane elementy dachu wykonano w tradycyjny sposób, z krokwią i jętkami. Pokrycie dachu zrobione jest z dachówki karpiówki ułożonej w koronkę, natomiast dach wieży jest pokryty dachówką mnich/mniszka. Podłogi w budynku różnią się w zależności od kondygnacji. Wszystkie posadzki wykonane są z płytek ceramicznych, ale na emporze organowej oraz na pierwszym i drugim piętrze wieży znajdują się podłogi z desek, które są pomalowane na biało. Otwory okienne i drzwiowe mają kształt ostrych łuków. Portal główny ma dwa uskoki, a następne pomieszczenia są jednouskokowe.[1]
[1] Zob. tamże, s. 141-142.