Mit dem Bau der Marienkirche wurde bald nach der Stadtgründung Neubrandenburgs 1248 begonnen.
Konzipiert war die Kirche ursprünglich als zweitürmige Feldstein-Basilika. Während des Baus wurde umdisponiert zur gotischen, dreischiffigen Hallenkirche in Backstein mit geradem Chorabschluss unter teilweiser Einbeziehung vorhandener Bauteile. Der Hauptaltar wurde 1298 geweiht. Es folgten die ersten vier östlichen Joche, danach die restlichen 5 Joche. In der zweiten Hälfte des 14. Jahrhundert wurde der Turm fertig gestellt.
Zur Zeit der Reformation in Neubrandenburg um 1523 gab es 39 Altäre in der Kirche. Große Beschädigungen gab es im 16. und 17. Jahrhundert durch mehrfache Blitzschlag und Brände. Der Bau wurde immer wieder notdürftig wieder hergerichtet.
Von 1832 bis 1841 fand eine umfassende Restaurierung der Kirche durch F.W. Buttel statt. Doch 1945 wurde die Kirche durch Brandstiftung stark zerstört. Nur Umfassungsmauern und Turmstumpf blieben erhalten.
Ein erster Versuch der Gemeinde, im Kircheninneren 1953 eine Notkirche zu errichten, scheitert. 1975 kauft die Stadt Neubrandenburg die Ruine. Man baute das Gebäude wieder auf mit dem Ziel, aus ihm einen Konzertsaal zu machen und im Dachgeschoss eine Kunstsammlung einzurichten.
1983 konnte man das neue Dach über dem Kirchenschiff und das Wiederaufsetzen der Turmspitze feiern. Mit der politischen Wende 1989/90 entschied man sich für eine vollständige Wiederherstellung der Außenhülle und des Turms.
Der Konzertsaal wurde ab 1996 durch den finnischen Architekten Pekka Salminen eingebaut. Die Konzertkirche gilt durch das Zusammenspiel aus historischer Hülle mit hineingestelltem Konzertsaal als eine der aufregendsten Konzerthallen Deutschlands. 2001 fand das Eröffnungskonzert statt.
Von einzigartigem architekturgeschichtlichen Wert ist der Ostgiebel der Kirche mit seinem vor die eigentliche Giebelwand vorgeblendeten schleierartigen Maßwerk. Hier wurden Formen der Hausteinarchitektur wie beim Straßburger Münster in Backstein übertragen, womit die Marienkirche eine neue Tradition im Backsteinland begründete.
Einzelformen des Giebels finden sich an den prächtig gestalteten Seitenportalen der Kirche, aber auch an den berühmten Neubrandenburger Stadttoren wieder. Spätere Bauten wie die Prenzlauer Marienkirche oder die Stettiner Kirchen von Heinrich Brunsberg stehen eindeutig in der Tradition des Neubrandenburger Vorbildes.
Im Kirchturm ist die Dauerausstellung „Wege zur Backsteingotik – In Neubrandenburg zur Wehr und Zier“ zu sehen.
