Afin de répondre aux exigences de modernisation du service postal, l’Administration des Postes et Télégraphes décide la construction d’un nouvel hôtel des postes à Rodez. Le projet est confié au montpelliérain Edmond Leenhardt, architecte régional des Postes et Télégraphes depuis 1923 et déjà auteur de plusieurs bureaux (Montpellier, Castelnaudary, Perpignan, Nîmes). Ce dernier dessine un premier projet daté 27 avril 1935 mais la version définitive n’est approuvée que le 7 août 1936.
Les travaux, réalisés par l’entrepreneur de travaux publics Maurice Bardet, débutent en décembre 1936 suite à la démolition de tout un îlot rue Louis-Blanc (immeubles privés et école Gally). Le bâtiment est achevé en avril 1939 et la réception définitive intervient en août 1940.
Dès les premières esquisses, Leenhardt avait prévu de décorer la façade d’une enseigne de marbre blanc portant l’inscription « Télégraphe - Poste - Téléphone ». Le panneau fut modelé par le sculpteur Marc Robert en 1938 puis exécuté en 1943 par le sculpteur montpelliérain Grand prix de Rome, Paul Guéry.
Le bâtiment est agrandi en 1961 avec la construction d’une aile en retour abritant la salle de tri et couverte d’une toiture terrasse, en harmonie avec le parti architectural d’origine. Un projet de surélévation est étudié au début des années 1970, mais il est finalement abandonné au profit d’une nouvelle construction avenue de l’Europe. L’Architecte des Bâtiments de France Pinard avait alors refusé l’avant-projet d’extension et formulé le 23 février 1972 le vœu suivant : « Pour faire pardonner la surélévation envisagée, il faudrait que ce rajout constitue une amélioration sensible du point de vue de l’esthétique de l’architecture existante, ce qui est loin d’être le cas ».
