La construction du palais de justice a été commandée par le maire de Millau, M. de Gaujal, pour la somme de 80 000 fr. L'adjudication a lieu en avril 1837 et la première pierre a été posée le 30 juillet (Artières, 1943). Il a été élevé par l'architecte départemental Etienne-Jospeh Boissonnade, auteur de l'orangerie de l'hôtel Sambucy-de-Sorgue et de l'hôtel de la sous-prefecture. Il s'élève à l'emplacement d'une partie du couvent des Cordeliers et remplace le tribunal d'origine médiévale situé à l'emplacement du palais des rois d'Aragon.