Cet espace situé sous la rue Royale est le plus ancien du site archéologique. Les murs dateraient du XIIe siècle. Le palais était un château-fort englobé plus tard dans les remparts de la première enceinte de Bruxelles datant du XIIIe siècle. Sous la duchesse Jeanne de Brabant et son mari Wenceslas de Luxembourg, au XIVe siècle, ce château devint une résidence agréable. Une deuxième enceinte cernait la ville et la résidence se transforma peu à peu en palais. Au-dessus de ces caves s’élevait le corps de logis, c’est-à-dire les appartements princiers avec leurs suites de salles d’audience et de chambres. C’est dans les appartements de la gouvernante générale Marie-Elisabeth que le feu se déclara durant la nuit du 3 au 4 février 1731.

Le corps de logis était constitué de trois étages avec de nombreuses fenêtres. De leurs appartements, les princes et leurs hôtes pouvaient observer les jeux qui se déroulaient dans les jardins ornés de pièces d’eau. Ils avaient aussi vue sur le grand parc où gambadaient des animaux en liberté. Un auteur précise que l’appartement de l’archiduc Albert au début du XVIIe siècle se situait au premier étage et celui de sa femme, l’archiduchesse Isabelle, au deuxième « les hommes [étant] séparez d’avec les femmes (…) à la mode d’Espagne » (Pierre Bergeron).

Le palais du Coudenberg était aussi le siège des institutions centrales des anciens Pays-Bas, principalement du Conseil d’État, du Conseil privé et du Conseil des finances. Siégeaient dans ces conseils des nobles, mais aussi des juristes et des financiers formés à l’université et chargés de donner des avis au gouverneur général. Ils étaient assistés par de nombreux secrétaires, greffiers et clercs. Sous les archiducs, le Conseil d’État se situait du côté du parc, juste avant la grande galerie. Au XVIIIe siècle, la salle du Conseil avec une antichambre se situait de l’autre côté de l’édifice, entre l’entrée du palais à la place des Bailles et la grande salle d’apparat.

La première enceinte de Bruxelles date du XIIIe siècle. À cette époque, la croissance démographique, économique et politique de la ville était suffisamment importante pour qu’elle se dote d’une muraille. Utile à la défense de la cité et signe extérieur de pouvoir, l’enceinte s’étendait sur un périmètre de quatre kilomètres et comptait sept portes. Le château du haut de la ville, situé sur la colline du Coudenberg, était englobé dans cette première enceinte urbaine. Dès le XIe siècle les comtes de Louvain, futurs ducs de Brabant, s’étaient installés sur la colline du Coudenberg.