Pendant de longues années, la localisation exacte du palais impérial de Charlemagne à Paderborn resta inconnue des chercheurs. Puis, en 1964, le mystère s’éclaircit : des premières traces archéologiques datant du 8^ème siècle sont retrouvées au nord de la cathédrale.

En plus des vestiges du palais carolingien, les archéologues mettent alors au jour des restes de la maçonnerie d’un autre palais impérial, celui de l’empereur Henri II. Leur état relativement intact permit même une restauration s’appuyant sur les fondations historiques du bâtiment.

À partir de 1978 sont exposés dans cette reconstitution du palais de Henri II des vestiges uniques de Paderborn et de sa région, remontant du 6^ème au 12^ème siècle : ainsi fut créé le musée du palais impérial de Paderborn.

Le musée est géré par le Landschaftsverband Westfalen-Lippe (LWL), et fait partie de la section archéologie du LWL. Le bâtiment est lui la propriété du chapitre de la cathédrale de Paderborn.

Du palatium des empereurs romains, situé sur la colline du Palatin à Rome, vient le mot "palais" : des constructions splendides, visant à établir physiquement la puissance du pouvoir régnant. Depuis l’époque carolingienne, les souverains germaniques pratiquaient ce qu’on appelle la royauté itinérante : au lieu d’une capitale centralisatrice, ils exerçaient leur pouvoir à partir de plusieurs lieux au sein de l’Empire, résidant dans les multiples palais. Jusqu’à l’époque des Hohenstaufen (11^ème - 13^ème siècle), ces palais se présentent la plupart du temps sous la forme de longues halles.

Au cours de ces itinéraires, les rois et les empereurs étaient accompagnés de leur entourage (famille, conseillers, clercs, guerriers, serviteurs) ; se rassemblant dans ce qu’on appelle la cour, ces derniers pouvaient gagner leur vie auprès du souverain. Cette cour itinérante comptait souvent plusieurs centaines de cavaliers et de piétons, et parcourait le royaume, allant d’un palais à un autre selon les besoins du souverain. Les palais avaient enfin une fonction militaire ; depuis la fin de l’époque carolingienne, ils étaient renforcés par d’épais murs destinés à prévenir d’éventuelles offensives.

Malgré que de nombreuses sources tendaient à indiquer que Charlemagne avait fait édifier un palais à Paderborn, les spécialistes cherchèrent pendant longtemps en vain des traces dudit palais. Seul un portique de pierre remontant à l’époque carolingienne semblait accréditer l’hypothèse selon laquelle un véritable trésor architectural se situait sous les mètres de gravats accumulés au fil de l’histoire tumultueuse de Paderborn. En 1963, alors que les clercs décident de remanier le terrain au nord de la cathédrale, les archéologues du LWL (Landschaftsverband Westfalen-Lippe) obtiennent l’autorisation de mener des fouilles sur la zone concernée par les travaux.

Rapidement, des murs sont mis à jour : les archéologues viennent en fait de retrouver la trace du palais de l’empereur Henri II, édifié en son nom par l’évêque Meinwerk de Paderborn. À cette surprise en succède une autre plus grande encore : d’autres murs encore plus anciens sont repérés. Après des années de recherche, le palais de Charlemagne à Paderborn est finalement découvert par l'archéologue Wilhem Winkelmann. Cette avancée majeure a marqué le début d’une série de recherches qui font du centre historique de Paderborn l’un des ensembles du genre les mieux étudiés en Europe.