Mit dem Bau der Marienkirche in ihrer heutigen Form wurde nach einem aus Quellen bekannten Turmeinsturz oder Einsturz des Turmhelms im Jahre 1384 begonnen. Langhaus, Querhaus und Chor entstanden nach relativ einheitlichem Plan von 1384 bis wahrscheinlich 1411/12 In einem zweiten Bauabschnitt entstand von 1418 bis 1473 das heutige Turmbauwerk mit dem westlichen Querhaus, das in sich eine quergelagerte Halle darstellt. In den folgenden fünf Jahren bis 1478 wurde der Turm mit einem enormen Spitzhelm bekrönt, der in 150 Metern Höhe endete und den Turm zu dem zum Zeitpunkt seiner Errichtung höchsten Bauwerk machte. Die gesamte Bauzeit der Marienkirche betrug somit 94 Jahre.

Bis 1647 stand die Marienkirche als größte Pfarrkirche der Hansestadt Stralsund in dieser Form. In jenem Jahr wurde die große Kirchturmspitze durch Blitzschlag zerstört; die Kirche erlitt in Folge des Brandes erheblichen Schaden mit Verlust der beiden westlichen Langhausgewölbe - erneuert 1651, der Dachstühle und der Holzanker. Eine dendrochronologische Untersuchung (T. Schöfbeck) datierte sämtliches Holz nach 1647. Die Wiederherstellung der Kirche dauerte 28 Jahre, bis 1675. Die heutige barocke Turmhaube wurde allerdings erst 1710 vollendet. Infolge der französischen Besatzung Stralsunds kam es in den Jahren 1805 bis 1810 zu erneuten Verwüstungen im Innenraum. Anschließend wurde die Kirche provisorisch wiederhergestellt. Bedeutend ist die grundlegende Restaurierungsmaßnahme der Jahre 1840 bis 1856, die allerdings zu einer Neugestaltung und Uminterpretation der Baudetails im Sinne der frühen Neugotik unter direktem Einfluss Karl Friedrich Schinkels führte. Heute ist das noch an der neugotischen Stuckdekoration des Chores zu erkennen, die es in der ganzen Kirche gegeben hatte, die aber in den 1920-er Jahren im Langhaus und teilweise auch im Querhaus zurückgenommen wurde. Aus dieser Zeit stammt auch der heutige gelbliche Fondton, der damals gegen den Protest der staatlichen Denkmalpflege aufgebracht wurde. Bei der damaligen Maßnahme wurden die zum Teil figürlichen Malereien in den Langhaus-Seitenschiffen entdeckt und bis Anfang der 1940-er Jahre freigelegt und ergänzt.