Pierwsza świątynia została wybudowana w 1416 roku. Kościół ten został zniszczony w czasie wojny trzynastoletniej (1454-1466). Odbudowany został w latach 1490-1500. W 1589 roku świątynia została przejęta przez protestantów. Kościół posiadał jedną nazwę oraz zakrystię od strony północnej. Od strony zachodniej mieściła się wieża. W 1599 roku król Zygmunt III Waza oddał świątynię katolikom, ale w 1626 roku luterańscy Szwedzi oddali go ponownie protestantom. Taka sytuacja trwała do pokoju oliwskiego zawartego w 1660 roku. W 1698 roku zostały zamontowane w świątyni nowe ławki, została założona drewniana podłoga, wnętrze zostało wymalowane i został wzniesiony chór. Wyremontowana została również zakrystia mieszcząca się wówczas niedaleko współczesnego północnego wejścia do świątyni. W 1774 roku zostały ufundowane organy o 12 głosach i został wzniesiony chór nad zakrystią. W 1899 roku kościół w Sztumie postanowiono częściowo rozebrać i przedłużyć o 10 metrów w stronę wschodnią według projektu Reimbotha z Iławy ze względu na jego duże zniszczenie. Prace zostały zakończone w 1901 roku. Stare, gotyckie mury można dzisiaj oglądać w części zachodniej, z kolei nawy boczne, główny korpus świątyni, prezbiterium i wieża reprezentują styl neogotycki, tak samo jak ogromna większość wyposażenia świątyni.

Do dawnego wyposażenia świątyni należą m.in.: dzwon, znajdujący się pod schodami prowadzącymi na chór, pochodzący z 1502 roku, późnogotycka, monstrancja, przerobiona w XVII stuleciu, cztery lichtarze z XVII wieku, dwie barokowe Stelle z podobiznami świętych znajdujące się obecnie na wzdłużnych ścianach obu naw bocznych, dwa rokokowe konfesjonały znajdujące się pod chórem, rokokowa chrzcielnica znajdująca się w południowej nawie, grupa ukrzyżowania znajdująca się nad ołtarzem głównym, renesansowa płyta nagrobna nakrywająca wcześniej grób Achacego Cemy wojewody malborskiego i starosty sztumskiego, zmarłego w 1565 roku oraz dwie anonimowe płyty nagrobne znajdujące się w posadzce pod rokokowymi konfesjonałami.