Suite à l'établissement du siège de la sénéchaussée du Rouergue à Villefranche-de-Rouergue, un bâtiment est construit en 1371, puis agrandi en 1551 suite à la création du Présidial. Occupant l'actuel emplacement du théâtre et de ses abords, le vieux palais de justice tombe en ruine au milieu du 19e siècle, malgré les réparations apportées depuis la Révolution. Dès 1838, l'administration décide de trouver un nouveau bâtiment susceptible d'accueillir le tribunal. Le projet d'une nouvelle construction reste en suspens. Suite à l'adoption, par le conseil général, du plan d'édification d'un tribunal similaire à Espalion (Aveyron) en 1843, une commission est constituée en 1844 pour rechercher un terrain. En 1851, la mairie vote des budgets pour l'édification du futur tribunal après avoir choisi la promenade du Guiraudet pour l'implanter. En 1853, l'architecte départemental Etienne-Joseph Boissonnade livre un premier plan de l'édifice au maire. La déclaration d'utilité publique est publiée le 23 mai 1853. Le 16 décembre de cette même année, le préfet demande à Boissonnade de modifier les plans. Le 30 septembre 1854, on annonce par voie d'affiche une nouvelle adjudication suite à la première demeurée infructueuse. La deuxième n'est pas plus concluante. Le nouvel architecte départemental Jean-Baptiste Vanginot modifie les plans mais le projet de construction reste en sommeil, suite à l'emploi des fonds départementaux pour le palais de justice d'Espalion. La première pierre du nouveau tribunal de Villefranche-de-Rouergue est solennellement posée le 19 mai 1861 par le préfet de l'Aveyron, Charles Demonts. Une boîte en plomb scellée est alors déposée dans la maçonnerie. Elle renferme sept pièces de monnaie courantes millésimées de 1860 ainsi que 11 médailles en bronze commémorant l'Algérie (1830-1853) par Pingret, l'élection du Président de la république (1848) par Caqué, le Voyage du prince président (1852) par Depaulis, Vox populi, vox dei (1852) par Depaulis, Rétablissement de l'empire (1852) par Depaulis, Prise de Bomarsund (1854) par Caqué, Bataille de l'Alma (1854) par Bovy, Voyage de la reine d'Angleterre (1856) par Gayrard, Exposition universelle (1855) par Borrel, Voyage de Victor-Emmanuel, roi de Sardaigne (1855) et naissance du prince impérial (1856) par Montagny. Mais la construction amorcée est bientôt suspendue. Le 20 janvier 1864, le préfet se plaint à l'architecte Vanginot de la lenteur des entrepreneurs. Les sculptures du fronton sont réalisées la même année par François Mahoux, élève de Gayrard. Le palais de justice est inauguré le 9 avril 1866. Suite à la réforme judiciaire de 1958, le tribunal de première instance (ex tribunal civil) est supprimé et transféré à Rodez. Le département confie les locaux du palais de justice à la commune de Villefranche pour gardiennage et entretien de l'immeuble, le 28 novembre 1959. Le 11 janvier 1968, le département cède le bâtiment à la commune qui transforme alors le palais de justice en mairie. En 1974, les locaux du tribunal d'instance sont installés à son emplacement d'origine, à savoir l'ancienne mairie.