À l'origine, l'emplacement est occupé par un ensemble de bâtiments religieux dont la chapelle Notre-Dame-des-Morts, un cimetière, l'église ainsi que le couvent de Notre-Dame fondé vers 1616[1].
Au début du XIXe siècle, l'église Notre-Dame est très dégradée, et une caserne de gendarmerie s'installe dans une partie du bâtiment.
La nouvelle halle est construite en 1837, et est inaugurée l'année suivante. Celle-ci, mêlant marché paysan et marché de gros, accueille également les services de la mairie avant leur déménagement en 1876 dans l'actuel bâtiment. Une promenade bordée de platanes est également aménagée autour de l'édifice à ce moment-là.
La place est alors également pourvue de plusieurs hôtels dont le Henri IV (actuel hôtel Le Bourbon), l'hôtel des Pyrénées et l'hôtel de l'Europe et Moderne.
Durant l'entre-deux-guerres, sous l'impulsion du maire Alfred de Lassence, le promoteur et homme politique Henri Lillaz s’intéresse à ce lieu en vue d'un réaménagement futur.
En ce sens, la nouvelle halle est démontée à partir de 1929 afin d'être déplacée vers la seconde halle construite en 1876, place des Écoles (actuelle place de la République). L'espace libéré constitue alors l'actuel parterre de la place[2].
Dans le même temps, l'ancien couvent Notre-Dame, devenu par la suite couvent des Ursulines, est également détruit.
Le palais des Pyrénées est construit dans le style "paquebot" déclinaison tardive de la mouvance Art déco et celui-ci est inauguré le par le maire Alfred de Lassence.
Un square elliptique est également aménagé sur le parterre du palais par le paysagiste Louis Decorges et agrémenté d'une élégante fontaine sur laquelle trône La Source statue en marbre blanc sculptée par Paul Auban en 1913.
Le palais des Pyrénées contient alors divers commerces comme une agence de voyages, des boutiques d'ameublement, des cafés, un casino, un mini golf et un concessionnaire automobile. La salle de spectacle accueille des artistes comme Édith Piaf mais également des combats de boxe avec Marcel Cerdan.
Entre 1951 et 1958, le palais est largement remanié. La coupole placée au centre du bâtiment ainsi que la colonnade couverte en dessous sont détruites en 1952 permettant ainsi de dégager la perspective sur les Pyrénées depuis la place Clemenceau au moyen d'un passage piétonnier devenant l'avenue de Lattre-de-Tassigny.
À partir de 1956, deux tours de logements sont construites sur les plans des architectes Delahalle et Jules-Antoine Noutary à la demande du maire Louis Sallenave.
En 2006, la municipalité décide de totalement rénover la place et le palais des Pyrénées. Un parking souterrain de 400 places est construit et la place devient dès lors entièrement piétonne avec l'installation d'une fontaine et de jets d'eau. Le palais des Pyrénées est entièrement rénové pour accueillir 16 enseignes commerciales sur 10 000 m2 et des bureaux sur 2 500 m2[3].
Emplacement de la future place Clemenceau en 1904 avant la destruction de la Nouvelle Halle.
.svg){kind=small}
