An der Nordseite des Domes liegt das Gebiet, in dem vor gut 1200 Jahren Paderborner und europäische Geschichte geschrieben wurde. 

Die Siedlung an den Paderquellen gewann Bedeutung in den 772 beginnenden, oft grausamen Sachsenkriegen Karls des Großen, die als "Schwertmission" die Erweiterung des Frankenreiches und die Ausbreitung des christlichen Glaubens miteinander verbanden. Neun Aufenthalte des Frankenkönigs im Paderborner Raum sind bezeugt. Er errichtete hier nun 776 eine "Stadt" Karlsburg, deren Befestigung den heutigen Dombereich umschloss. Sie reichte nach heutigen Bezeichnungen vom Schildern, der Straße zwischen Rathaus und Markt, durch den Kötterhagen, die Krumme Grube um das Gerichtsgebäude, führte dann nach Norden, umschloss das Konrad-Martin-Haus am kleinen Domplatz und führte nach Westen auf das östliche Paderquellbecken zu, an dessen Südseite sie dann bis über die Michaelstraße verlief, um hinter den Häusern an deren Westseite und hinter dem Fürstenhof am Abdinghof wieder auf den Schildern zuzugehen. In dieser Karlsburg wurden im Jahr 776 Sachsen in großer Zahl getauft.

Im Nordwestbereich der Burg erbaute Karl der Große eine Königspfalz, deren Grundmauern nördlich des Domes ausgegraben worden sind. Die Herrscher des mittelalterlichen Reiches, das noch keine feste Hauptstadt kannte, residierten in Pfalzen. Wichtigstes Gebäude derselben war eine innen wie außen reich geschmückte Königshalle. Von dem in Paderborn ausgegrabenen karolingischen Saalbau wurden Reste einer Ausmalung mit einer Inschrift gefunden, die vermutlich Karl als den Sieger über den Drachen, das Heidentum, feierte. Wohngebäude, Höfe, eine Kirche und ein Missionskloster, das nördlich des Langhauses des heutigen Domes lag, schlossen sich nach Osten hin an. Zur Versorgung der Pfalz wurde ein Krongutsbezirk geschaffen, dessen Haupthof Enenhus in der Nähe der heutigen Georgskirche an der Neuhäuser Straße lag.

In dieser Burg "Paderbrunnon" (Paderbrunna, Patresbrunna, Patrebrunna, Patrisbrunna) hielt Karl nun 777 die erste der jährlichen fränkischen Reichsversammlungen auf sächsischem Boden. Die Großen des Reiches und der König trafen sich hier zur Ordnung Sachsens und zur Einteilung der Missionsbezirke. Paderborn wurde der Würzburger Kirche zugewiesen. Erneut erfolgte eine Massentaufe der Sachsen. Ein Gedicht über die Sachsenbekehrung in dem Hofstil der damaligen Zeit verglich schon das Erscheinen Karls in Sachsen mit dem Christi zur Rettung dieser Welt. Araber erbaten in Paderborn eine Intervention des Frankenherrschers in Spanien, die dann im folgenden Jahre zur Niederlage im Tal von Ronceveaux führte, von der die Rolandssage erzählt. Die Sachsen nutzten Karls Abwesenheit zu einem großen Aufstand unter Widukind, zerstörten 778 alle in Paderborn von den Franken errichteten Gebäude und brachten über den Resten der Dracheninschrift Pferdeopfer dar.
Karl gab nicht auf, ließ zahlreiche Sachsen töten und erbaute die Pfalz noch stärker als zuvor. Paderborn blieb Versammlungspfalz des Herrschers für Sachsen. Wichtige Gesetze wurden hier erlassen, und mit der Taufe Widukinds im Jahr 785 schien die Einbeziehung Sachsens in das Frankenreich vollzogen. Doch ein neuer Aufstand in den 90er Jahren zerstörte wiederum die Pfalz an den Paderquellen. Noch einmal entstand sie neu. Nun wurde auch im Bereich des heutigen Domes eine dreischiffige Basilika als Bischofskirche für das hier vorgesehene Bistum gebaut. Im Hof vor der Pfalzhalle, vor dem Durchgang zur älteren Kirche, wurde ein Stufenbau errichtet, der ursprünglich als Unterbau eines Außenthrones gedeutet wurde. Neuere wissenschaftliche Erkenntnisse haben jedoch ergeben, dass es sich "nur" um eine Treppe handelt, die auf ein Podest zwischen Aula und Dom führte.

In diese Pfalz lud Karl im Jahre 799 Papst Leo III. ein. Der Frankenkönig war bereits auch Herrscher der Langobarden, zudem Schutzherr der Römer. Eine Verschwörungsgruppe gegen Leo III., geführt von Verwandten seines adligen Vorgängers, hatte den Papst bei einer Bittprozession überfallen, abgesetzt und eingesperrt. Leo III. war entkommen. Karl ließ ihn nun nach Paderborn geleiten. Ein noch in diesem Jahr entstandenes Gedicht mit 536 lateinischen Hexametern, das sogenannte  "Paderborner Epos", schildert die feierliche Einholung und den festlichen Empfang des Papstes in Paderborn, läßt aber auch erkennen, dass Karl sich bereits als der "Vater Europas", als dessen Leuchtturm und als Augustus empfand. Der Papst bot ihm die Krönung zum Kaiser an, die Franken sollten Reichsvolk, Aachen das neue Rom sein. Doch der Herrscher ließ sich von Leo III., dessen Legitimität durch Abgesandte seiner römischen Gegner bestritten wurde, nicht krönen. Erst als sich im folgenden Jahr der Papst in Rom durch einen Eid von den Vorwürfen seiner Gegner gereinigt hatte, konnte er durch die Krönung Karls das römische Kaisertum erneuern.

Der Königssaal der einstigen karolingischen Pfalz wurde nicht wieder aufgebaut. Die von Archäologen freigelegten Mauerreste hat man an der Oberkante begradigt, um die Zersetzung durch Witterungseinflüsse zu verhindern. Ursprüngliches Mauerwerk ist dabei von ergänzten Partien durch flache Tonziegel optisch getrennt.

An den karolingischen Pfalzbereich grenzt nördlich die ottonisch-salische Kaiserpfalz aus dem 11. und 12. Jahrhundert. Der 44 Meter lange und 16 Meter breite Saalbau sowie einige kleinere Nebengebäude sind von 1976 bis 1978 auf den alten Grundmauern bei größtmöglicher Bewahrung ursprünglicher Bausubstanz neu errichtet worden.
Während im Obergeschoss der großen Halle kulturelle Veranstaltungen stattfinden, dienen das Untergeschoss sowie einige benachbarte Räume als Museum.