Une ancienne mairie-halle existait sur la place de Fleurance avant la construction de celle-ci mais elle a été démolie à la suite d’un incendie en août 1833. Il s’agissait d’une halle portée par 28 poteaux de bois contre laquelle était adossé un petit bâtiment faisant office de maison commune. Dès 1829, la commune avait souhaité la reconstruction de la halle et de l’hôtel de ville, en y adjoignant la justice de paix et les écoles.

L’architecte Ardenne, installé à Auch, propose un premier projet très ambitieux qui est retoqué par le Conseil des bâtiments civils en juin 1833. Parmi les nombreuses modifications demandées par le rapporteur figurent notamment le fait de séparer les écoles de la mairie-halle, ainsi que la nécessité d’exhausser la partie centrale de l’édifice afin d’éclairer le corridor. Malgré cela, le plan d’ensemble de l’édifice tel qu’on le connait aujourd’hui est déjà en place avec la halle au rez-de-chaussée et l’hôtel de ville à l’étage, organisés autour d’un vaste espace central ouvert.

En février 1834, le Conseil des bâtiments civils retoque à nouveau le projet d’Ardenne au motif que certaines pièces ne peuvent être chauffées et que d’autres manquent d’éclairage. Le rapporteur suggère la réalisation de sept arcades au lieu de cinq sur chacun des côtés de la halle afin d’en améliorer la solidité. Le projet est enfin accepté en août 1834 avec quelques réserves concernant notamment les cheminées et la hauteur de la lanterne. Le devis est alors très légèrement inférieur à 50 000 fr (avec l’utilisation d’une partie de matériaux de récupération de l’ancienne halle).

Les travaux débutent dès 1834 et sont achevés en 1837 (date inscrite au-dessus de la baie centrale du balcon d’honneur de la façade est).

Les statues situées aux angles de la mairie-halle sont inspirées des nymphes de la fontaine des Innocents à Paris et des modèles du sculpteur Albert-Ernest Carrier-Belleuse. Elles ont été fondues par Durenne dans son atelier de Sommevoire en Haute-Loire (marque). Ces statues ont été données par Adolphe Cadéot, maire de Fleurance au 19e siècle.