Ein um 1220 errichteter Vorgängerbau wird 1234 in einer Urkunde Heinrichs (VII.) erwähnt. Heinrich hatte von seinem Vater Friedrich II. den Auftrag erhalten, nördlich an die Stadt Nordhausen angrenzend einen neuen Stadtteil mit einer Kirche anzulegen, den Hagen. Im Unterbau der Kirchtürme sollen sich noch Überreste dieses Vorgängerbaus befinden. Die Kirche wurde dem Domstift unterstellt. 1487–1490 wurde das Schiff durch einen Neubau ersetzt, der an die spätromanisch-frühgotischen Westtürme des Vorgängerbaus angebaut wurde. Die Jahreszahl 1489 findet sich auf einem Schlussstein des Chorgewölbes.
Nach der Reformation, 1524 übernahm Johann Spangenberg auf Empfehlung Martin Luthers die Stelle des ersten evangelischen Predigers. Dieser machte sich durch Schulunterricht und Herausgabe erbaulicher Schriften auch über die Gemeinde hinaus verdient.
Den Stadtbrand des Jahres 1612 überstand die Kirche unbeschadet. Am 24. April 1634 traf ein Blitzschlag den nördlichen Kirchturm, sodass der Turmhelm abbrannte. 1687 wurde zur Sicherung der Kirchtürme ein Strebepfeiler an die Westseite der Kirche angebaut. Dabei wurden Steine der Walkenrieder Kirchenruine verwendet. Auch den nächsten großen Stadtbrand am 21. August 1712 überstand die Kirche schadlos, während das Pfarrhaus vollständig niederbrannte.
Die Kirche erlitt beim Luftangriff auf Nordhausen am 4. April 1945 erhebliche Schäden an den Dächern und dem Mauerwerk, besonders der Ostteile. Die Cranach-Gemälde waren in einen Brauereikeller ausgelagert worden und verbrannten dort. Bis 1949 wurden die Dächer wiederhergestellt, das Mauerwerk wurde ausgebessert und das Innere erneuert.
Eine wegen Einsturzgefahr der Türme und des Dachs erfolgte Restaurierung der Kirche wurde 2004 abgeschlossen. Eine Sanierung des Innenraums schloss sich 2014 und 2015 an.