Bis ins 19. Jahrhundert war der Markt der größte Platz der mittelalterlichen Domfreiheit. Allerdings hieß der Platz bis in das 17. Jahrhundert „Kohlgrube“, was auf die im Süden der Domburg gelegenen Steinbrüche hinweist, in denen vor Ort das Steinmaterial zum Häuserbau gewonnen wurde. Bereits im frühen Mittelalter war die „Kohlgrube“ ein Ort des Marktgeschehens, denn bis zum 12. Jahrhundert war die Stadt ein bedeutender überregionaler Handelsort. In West-Ost Richtung verlief hier einer der bekanntesten Handelswege: Der Hellweg. Das damalige Straßen- und Platzniveau in der Domburg und dem angrenzenden Bereich lag allerdings ein bis drei Meter tiefer, als heute.

Schon im 14. Jahrhundert entsprach der Marktplatz mit den ihn umgebenden Gebäuden in etwa seiner heutigen Form.

Im 17. Jahrhundert gewann die „Kohlgrube“ immer mehr an Bedeutung, durch die Verlagerung des ständigen gewerblichen Marktes aus dem westlich angrenzenden Bereich, auf den nun als „Markt“ bezeichneten Platz.

1730 wurde der Handel auf dem Friedhof untersagt und der Markt bekam sein Wahrzeichen, den Neptunbrunnen. Nur 100 Jahre später wurde der Markt neu gepflastert. Außerdem wurden zwei wöchentliche Markttage eingeführt. Dieser Turnus hat sich bis heute nicht geändert.

Nach dem Wiederaufbau nach 1945 wurde der Markt auch zeitweise als Parkplatz genutzt. Im Rahmen des Wiederaufbaus wurde auch ein neuer Neptunbrunnen von dem Paderborner Bildhauer Josef Rikus entworfen und der Platz erneut neu gepflastert. 1979 war die Umgestaltung des Marktes damit abgeschlossen.

Auch die Gebäude um den Markt herum wurden 1945 stark beschädigt oder ganz vernichtet. Einzig die Gaukirche kam mit relativ geringem Schaden davon und wahrte zusammen mit den bürgerlichen, barocken Häusern an der Südwestecke beim Wiederaufbau ihr altes Erscheinungsbild.

Die Westfront des Marktes wurde nach dem Zweiten Weltkrieg teilweise nur zweigeschossig wieder aufgebaut, während die Ruinen der nördlichen Häuserzeile vor dem Dom beseitigt wurden. Erst durch den Museumsbau 1975 wurde die alte bauliche Situation an der Nordwestecke durch Gottfried Böhm mit modernen Formen wieder hergestellt.