Das Bistum Halberstadt wurde im ersten Jahrzehnt des 9. Jahrhunderts als Missions- und Verwaltungsmittelpunkt im neu eroberten sächsischen Stammesgebiet errichtet.
Als erste Bischofskirchen dienten kleinere Steinbauten, denen ein 859 geweihter karolingischer Neubau in Form einer dreischiffigen kreuzförmigen Basilika folgte. Dieser Dom stürzte im Jahr 965 ein, unmittelbar danach begann der Bau des ottonischen Doms, der 992 geweiht wurde und schon fast die Ausmaße des späteren gotischen Neubaus erreichte. Im 10. Jahrhundert trat das nahe Magdeburg, das immer mehr als Zentrum ottonischer Herrschaftspolitik diente und in dem Otto I. 968 ein Erzbistum auf Kosten der hiesigen und der Merseburger Diözese installierte, zunehmend in Konkurrenz zu Halberstadt. Die (ottonische) Kathedrale wurde im Zuge der Zerstörung der Stadt 1179 durch Heinrich den Löwen schwer beschädigt, aber anschließend rasch restauriert und neu eingewölbt (Weihe 1220).
1209 begann das konkurrierende Magdeburger Erzstift mit dem Bau eines Domes, der stark von der Architektur der französischen Kathedralgotik beeinflusst war. Das Halberstädter Domkapitel beschloss nun seinerseits den sukzessiven Bau einer „modernen“ gotischen Kathedrale, der ungewöhnlicherweise mit dem Westbau begonnen wurde. Das Kapitel wollte den bestehenden Dom noch möglichst lange weiter nutzen, war doch noch kurz zuvor für die Einwölbung viel Geld investiert worden.
Der Westbau verbindet die lokale spätromanische Bautradition mit den modernen frühgotischen Einflüssen, insbesondere der Architektur der Zisterzienser. Der obere Teil der heutigen Westfassade ist allerdings größtenteils dem 19. Jahrhundert zuzuordnen.
Um 1260 begann der Bau des hochgotischen Langhauses, dessen Dimensionen – wohl wieder als Konkurrenz zu Magdeburg, gegenüber der ursprünglichen Planung wesentlich gesteigert wurden. Das Mittelschiff erreicht die für damalige Verhältnisse beeindruckende Höhe von 27,0 m, die Seitenschiffe sind 14,0 m hoch. Allerdings wurden in dieser zweiten Bauphase nur die ersten drei Joche des Langhauses gebaut, man musste ja den alten Dom funktionsfähig erhalten. Im Gegensatz zu Magdeburg orientieren sich diese ersten Joche wesentlich näher an den französischen Vorbildern, besonders das offene Strebesystem ist hier voll entwickelt, allerdings in „deutscher“ Reduktion. Als Vorbild dürfte hier die Kathedrale von Reims gedient haben. Wegen der notorisch schlechten Finanzsituation des Domkapitels zog sich der Bau allerdings über etwa 50 Jahre hin.
Da sich die finanzielle Lage des Bistums so schnell nicht besserte, beschloss man, den alten Dom noch eine Weile weiter zu nutzen, und begann um die Mitte des 14. Jahrhunderts am entgegengesetzten Ende mit der Errichtung der Marienkapelle. Um 1350 begannen die Abbrucharbeiten für den Chorbau, der sich an den Maßverhältnissen der westlichen Langhausjoche orientierte. Dieser Bauabschnitt dauerte wiederum etwa 60 Jahre bis zur Weihe im Jahre 1401. Später wurden noch einige Kapellen hinzugefügt.
Der Dom muss nun ein etwas seltsames Bild geboten haben, denn zwischen den gotischen West- und Ostteilen lag ja noch das ottonische Langhaus. Diesen Zustand wollte man nicht lange hinnehmen, die Bauarbeiten für die fehlenden gotischen Ostjoche des Langhauses und das Querhaus dürften wohl kurz nach der Chorweihe begonnen haben. Nach weiteren 90 Jahren konnte die gesamte Kathedrale eingeweiht werden (1491).
Als letzte spätgotische Ergänzung wurde 1514 der neue Kapitelsaal fertiggestellt (Gewölbe 1945 zerstört), und 1516 kam der bronzene Radleuchter im Mittelschiff hinzu.
Die folgenden Jahrhunderte – bis zum Ende des Zweiten Weltkrieges – bewahrten im Wesentlichen das mittelalterliche Erscheinungsbild; die größte Baumaßnahme war hier die erwähnte Neuaufmauerung der Westtürme.
Der 8. April 1945 brachte schließlich den Untergang des alten Halberstadt mit seinen über tausend erhaltenen Fachwerkhäusern. Auch der Dom wurde von 12 Bomben schwerst getroffen. Während die Altstadt nach dem Krieg weitgehend dem Verfall preisgegeben wurde, unternahm die DDR-Denkmalpflege umfangreiche Maßnahmen zur Sicherung und Wiederherstellung der großen gotischen Kathedrale. Die Restaurierung wurde nach der Wende fortgesetzt.
Am 15. September 2010 wurde wieder ein Dachreiter über der Vierung angebracht.
