Fundacja. Pierwszy, romański kościół na wyspie powstał z fundacji rodu Piotra Włostowica. Świątynia jest poświęcona Najświętszej Marii Pannie, patronce Marii Włastowej — żony możnowładcy, przedstawionej na tympanonie, jak klęczy przed Madonną.
Gotycka hala. W XIV wieku romański kościół rozebrano, a w latach 1334–1430 wzniesiono ceglany gotycki według planów mistrza Peschela. Nawa ma 78 m długości, a sklepienia wznoszą się na ok. 24 m; wieża północna nigdy nie została ukończona. W 1632 roku kościół złupili Szwedzi, w 1666 roku Antonio Coldin zbudował kaplicę Świętego Krzyża — uważaną za najstarszą budowlę barokową w mieście — a w czasie wojny siedmioletniej Prusacy urządzili tu skład amunicji.
Zniszczenie i odbudowa. W 1945 roku kościół był siedzibą sztabu niemieckiego i spłonął; zginęły barokowy wystrój, obrazy Michaela Willmanna, ambona Franza Josepha Mangoldta i organy. Odbudowę rozpoczęto w 1946 roku, gdy stały tylko mury. Z dawnego wyposażenia zachowały się jedynie tympanon i chrzcielnica; wnętrze uzupełniono elementami z innych zniszczonych kościołów i z muzeum diecezjalnego. W 1968 roku Teresa Reklewska wykonała nowe witraże ze scenami z Nowego Testamentu. Kościół ma też XVI-wieczną figurę Madonny, podarowaną przez katolików z Mariampola w Besarabii. Od 1994 roku jest częścią Pomnika Historii.