Selon certaines sources, l'édifice devrait son nom à une légende du Moyen Âge, qui l'interprète comme un palais, et attribue sa construction à Charlemagne pour son épouse Galiene. Cette attribution est reconnue comme erronée, car l'édifice est un amphithéâtre romain dont le pourtour ovale se lit bien sur la vue aérienne de la ville de Bordeaux.
D'autres sources indiquent que le Palais Gallien doit son nom à l'empereur Gallien, qui régna de 253 à 268. Cependant, la technique de construction semble antérieure au règne de ce prince. Des monnaies de Gallien, Tétricus et Postume ont été découvertes dans les fouilles de l'édifice, ainsi que des tessons de céramique du IIIe siècle, mais on y a aussi découvert un bronze du règne de l'empereur Trajan, ce qui entretient le doute sur la date de construction. Un programme de fouilles, actuellement en cours et prévu pour une durée de 3 ans, a notamment pour but de dater plus précisément le monument.