Poza zamkiem krzyżackim, kościół ś. Mikołaja jest najbardziej monumentalną budowlą miasta, pochodzącą z okresu średniowiecza. Drewniana kaplica istniała w Gniewie prawdopodobnie przed przejęciem grodu w 1282 roku przez Zakon Krzyżacki.
W akcie lokacyjnym z 1297 roku jest wzmianka „…Ecclesiae parochiali…” tzn. parafialny kościół, który wyposażono w cztery włóki ziemi zwolnione z danin i ciężarów. Budowę obecnego kościoła rozpoczęto w połowie XIV wieku. Najpierw wybudowano prezbiterium. Prace budowlane związane z korpusem i wieżą przeciągnęły się do połowy XV wieku. Cokół kościoła składa się z potężnych płyt granitowych.
Większość wyposażenia świątyni pochodzi z drugiej połowy XIX wieku. Nie brakuje tu też cennych przedmiotów o dłuższym rodowodzie – ornat barokowy pochodzący z czwartej ćwierci XVII w., który wedle miejscowej tradycji ofiarowała parafii królowa Maria Kazimiera Sobieska.
Mniej więcej na ten też okres datuje się monstrancję wykonaną przez Krystiana Schuberta II – złotnika gdańskiego, jedną z najcenniejszych w tej części Polski, z glorią w kształcie słońca i sześciolistną stopą, na którą nałożone są plakietki ze scenami z życia Chrystusa.
W jednej z dwóch naw bocznych, zwanej kaplicą Radziwiłłów od nazwiska prawdopodobnego jej fundatora Stanisława Albrechta Radziwiłła – starosty gniewskiego, znajduje się ołtarz św. Jana Pawła II.
W latach 2009-2016 roku kościół w Gniewie oraz teren przykościelny był areną regularnie prowadzonych badań archeologicznych, w wyniku których odkryto m.in. największą w Polsce kolekcję szat jedwabnych, masowe groby, niezliczoną ilość monet, a także pozostałości wcześniejszej pogańskiej świątyni. Dzięki pracy archeologów możliwe stało się udostępnienie dla zwiedzających krypty, w której wyeksponowano część znalezisk.
Z XVIII stulecia pochodzi zawieszony na wieży kościelnej dzwon, noszący imię patrona świątyni. Na płaszczu dzwonu ludwisarz umieścił napis: „Zrodziła mnie pobożna szczodrość podwalin Kościoła”.