Powstanie Szczytna datuje się na XIV w., związane jest z budową zamku krzyżackiego. Historycy jednak spierają się o tę datę, gdyż już w 1266 r. istniała tutaj drewniana strażnica. Nie ma natomiast wątpliwości odnośnie powstania pierwszej parafii, dokumenty mówią wyraźnie o istnieniu kościoła już w 1493 roku. Niestety w czasie reformacji, ta jedyna świątynia katolicka została przejęta przez protestantów, a katolickie msze św. odprawiane były sporadycznie przez dojeżdżających kapłanów. Od roku 1834 przyjęło to już formę regularnych nabożeństw. W 1874 r. postawiono kaplicę, przydzielono stałego duszpasterza, co zaowocowało 16 stycznia 1893 r. ponownym erygowaniem parafii.
Istniejący dzisiaj kościół został wybudowany w latach 1898 – 1900, konsekrował go 2 lipca 1901 r. biskup warmiński Andrzej Thiel ku czci Wniebowzięcia N.M.P i św. Walentego. W tym czasie mieszkało w Szczytnie ok. 6 tyś. Osób, w tym tylko 300 katolików. Początki istnienia budowli nie były szczęśliwe; w 1905 r. na skutek uderzenia pioruna zniszczeniu uległa wieża, dzwony i organy. Kościół mocno ucierpiał podczas i wojny światowej, zniszczenia były tak poważne, zwłaszcza górna część wieży, że odbudowano go dopiero w 1923 roku. Bardziej łaskawa była II wojna światowa, miały miejsca jednak grabieże wotów i sprzętu liturgicznego. Mieszkańcy, którzy pozostali w mieście starali się zabezpieczyć ten obiekt sakralny przed całkowita dewastacją.
Sama konstrukcja świątyni jest bardzo typowa, jeśli chodzi o ten region; zbudowana z czerwonej cegły, styl neogotycki, murowana, wysoka wieża. We wnętrzu uwagę zwraca prospekt organów, trzy przedsoborowe ołtarze i ambona – rzeźbione w stylu również neogotyckim, ukazują Wniebowzięcie N.M.P w otoczeniu świętych. Po roku 1980 z powojennych granic parafii erygowano cztery następne, świadczy to o rozwoju miasta w zroście liczby mieszkańców. Kościół wielokrotnie odnawiano, w 1983 r. wieżę pokryto blachą miedzianą. Na 100 – lecie istnienia parafii i przed II tysiącleciem chrześcijaństwa w Polsce, ks. Arcybiskup Metropolita Warmiński Edmund Piszcz podniósł świątynię do godności Kościoła Jubileuszowego.