Historia Budowa kościoła rozpoczęła się na przełomie XIV i XV wieku w miejscu dawnej budowli na wzgórzu nad Wisłą. W 1538 roku została konsekrowana i oddana do użytku. Jego bryła została stopniowo uzupełniona rozbudowami: w 1565 r. powstała od północy kaplica pw. Jedenastu Tysięcy Dziewic, obecnie pw. Pięciu Ran Chrystusa i św. Zyty, w 1580 r. dostawiono od zachodu wieżę, w 1622 powiększono prezbiterium o półkolistą apsydę, a w 1635 r. dobudowano od południa kaplicę pw. Aniołów Stróżów, obecnie pw. Matki Boskiej Szkaplerznej.
W 1780 roku dobudowana została niewielka wieżyczka na środku dachu kościoła.
W przeszłości fara bywała wiele razy zalewana w wyniku powodzi. Dwie takie powodzie upamiętniają wyryte na cegłach ściany daty. Dopiero powstanie Bulwarów w XIX wieku zapobiegło zalewaniu kościoła.
W 1650 roku erygowano bractwo Aniołów Stróżów, którzy opiekowali się kaplicą południową. Wcześniej opiekował się nim cech krawiecki. Umieszczono w nim ołtarz Św. Barbary i Klemensa, nad którym pieczę sprawował cech rybacki.