Die Sankt-Nicolai-Kirche geht auf die Tradition von insgesamt 5 Kirchengebäuden zurück, die im Laufe der Jahrhunderte im Ort Neustadt bei Magdeburg bestanden und Sankt Nicolaus, als Schutzpatron der Elbschiffer, geweiht waren.

Der Bau einer ersten St. Nicolaikirche erfolgte ab circa 1150. Im Zusammenhang mit den Streitigkeiten zwischen Otto IV. und dem Erzbischof von Magdeburg ließ Otto IV. die Neustadt und die umliegenden Gebiete verwüsten. Dem fiel auch die Kirche zum Opfer.

Es wurde eine zweite St. Nicolaikirche errichtet, die jedoch bereits 1481 wegen Baufälligkeit wieder abgerissen wurde.

Der dritte Bau wurde zwar umgehend begonnen, die Einweihung erfolgte aber erst 1528.

Bereits am 1. April 1554 wurde das Gebäude erneut abgerissen, diesmal auf einen Befehl im Zuge der Belagerung der Stadt Magdeburg.

Die vierte Kirche wurde am 20. Mai 1585 durch den evangelischen Prediger am Magdeburger Dom Dr. Siegfried Sack eingeweiht. Während der Zerstörungen im Dreißigjährigen Krieg wurde auch diese Kirche wieder stark beschädigt.

Der fünften St. Nicolaikirche war ein längeres Bestehen vergönnt. Die Einweihung erfolgte am Palmsonntag des Jahres 1654.

Erst als während der französischen Besetzung im Jahre 1813 auf Befehl Napoleons die Magdeburger Vororte Neustadt und Sudenburg für ein verbessertes Schussfeld bzw. zum Ausbau der Festung Magdeburg weitgehend abgerissen wurden, wurde auch diese Kirche am 27. März 1813 durch Sprengung zerstört.

Während der Zerstörung der Neustadt durch Napoleonische Truppen wurde auch die St. Nicolai-Kirche am 27. März 1813 gesprengt. Den Neustädter Bürgern wurde etwas weiter nördlich ein neues Gebiet zur Ansiedlung zugewiesen. Dort entstand die Neue Neustadt.

Karl Friedrich Schinkel erhielt 1817 den Auftrag für den Entwurf einer Kirche für den neuen Ort. Es handelte sich um seinen ersten Kirchenbau. Schinkel schlug zunächst einen an der Gotik orientierten Bau vor. Der Entwurf wurde jedoch aus Kostengründen nicht umgesetzt.

Ein zweiter Entwurf, der von Johann Conrad Costenoble in Abstimmung mit Schinkel erstellt wurde, wurde vom Magdeburger Stadtkommandanten wegen eines zu hohen Turms abgelehnt. Es wurde ein möglicher feindlicher Einblick in die Festung befürchtet.

Für den dritten Entwurf erfolgte dann 1821 die Grundsteinlegung. Der Bau wurde durch den preußischen Staat unter Friedrich Wilhelm III. finanziell unterstützt.

Die Einweihung fand am 10. Oktober 1824 statt. Die St. Nicolai-Kirche soll als Vorbild für die später von Schinkel entworfene Normalkirche gedient haben.

1845 Erhöhung der Kirchtürme um ein Geschoss

1849 Einbau einer Kirchenuhr

1858 Renovierung des Kircheninnenraums

1862 Einbau der Orgel.

1860 Einbau des Glockengeläut

1866 Einbau einer Gasbeleuchtung mit 102 Flammen

1870 Einbau einer Heizung.

Im letzten Jahrzehnt des 19. Jahrhunderts fand eine erneute Restaurierung der Kirche statt.

So wurden auch ein neuer Altar und bunte Glasfenster angeschafft.

1934 Umbau, im Zuge dessen wurden Einbauten auf der Westempore entfernt und der aus dem Jahr 1712 stammende Taufstein von seinem mittigen Standort vor dem Altar vor den linken Chorbogen umgesetzt

Im Zweiten Weltkrieg wurde die Nicolaikirche bei einem Luftangriff am 29. September 1944 durch eine Sprengbombe getroffen. Die Bombe schlug in den Südturm ein. Das obere Stockwerk dieses Turms, aber auch Teile des Dachs und der Tonnendecke des Kirchenschiffs wurden zerstört. Weitere Schäden entstanden, als nach Kriegsende in der Nähe der Kirche befindliche Bunkeranlagen gesprengt wurden.

Der Wiederaufbau begann 1946 und war im Wesentlichen bis 1954 abgeschlossen. Das mittlere Fenster der Apsis wurde in diesem Zusammenhang zugemauert. Für diese Fläche schuf der Maler Günther Johl-Stenal das Wandbild „Durchbrecher aller Bande“.

Im Jahr 1993 stürzte an der Südseite der Kirche das Traufgesimse ein. Es wurden umfangreiche Sanierungsarbeiten eingeleitet, die auch eine Erneuerung des morschen, von Kernfäule betroffenen Dachstuhls, eine neue Deckung des Dachs mit Schiefer und eine Erneuerung der Tonnendecke umfassten.

Die Kirche wurde als Saalkirche im klassizistischen Stil errichtet, wobei die Gestaltung der Fenster sich an die Romanik anlehnt. Das Kirchengebäude ist verputzt und trägt ein Satteldach. An der Ostseite befinden sich zwei quadratische vierstöckige Türme, die den Chor flankieren und mit Walmdächern versehen sind.

Der Zugang befindet sich auf der Westseite, die von einem großen Dreiecksgiebel überspannt wird.

Durch Lisenen wird die Westfassade in drei gleich große Bereiche unterteilt.

Jeder dieser Bereiche trägt eine große Inschrift:

"IM KRIEGESDRANG ZERSTÖRT 1813"

"MIT GOTT DURCH KÖNIGSHULD"

"IM FRIEDEN HERGESTELLT 1824".

Innen befinden sich seitlich zweirängige Emporen. Die Decke wurde als kassettierte Tonnenwölbung ausgeführt. Dem rechteckigen Chor folgt eine halbkreisförmige Apsis, die über drei Fenster mit einer Höhe von 7,50 Metern verfügt.Das Kirchenschiff hat auf den Längsseiten jeweils sechs hohe Rundbogenfenster.

In der Kirche befindet sich ein Taufbecken aus dem Jahr 1715. Dies entstammt dem Vorgängerbau in der Alten Neustadt.