Cette résidence habituelle des ducs d'Aquitaine a été construite progressivement à partir de la fin du XIe siècle à l’angle sud-est de l’enceinte gallo-romaine, à l'emplacement de l'actuelle place du Palais.
Il intégrait probablement des éléments de la muraille gallo-romaine comme le suggère la figuration d’une tour construite dans un appareil de moellons et d’arases de brique, dite « tour de la Chître » .
Le palais a été construit peu à peu sans plan d'ensemble autour de la tour de « l’Arbalesteyre ». C'était un donjon implanté à 40 mètres en avant du rempart, sous forme d'une grosse tour rectangulaire de 18 mètres sur 14 sans escalier intérieur. Son nom était du à son adossement à une caserne où logeaient les arbalétriers royaux. Devant le Palais s’étendait la place en triangle dite "du Palais ".
L’Ombrière resta jusqu'à la Révolution le siège des tribunaux et la prison principale de Bordeaux. Pendant la Révolution française, le palais et la place prirent le nom de Brutus, référence à l'Antiquité assez courante à cette période. Le palais Brutus servit de prison.
Après divers incendies (1597, 1704), il fut démoli en 1800 et la rue de l'Ombrière a été ouverte à sa place.
