Le pont Lerouge est élevé au début du 19e siècle en remplacement d'un pont plus ancien, le Pont Vieux (IA12100870) élevé au début du Moyen Age et qu'une crue du Tarn a détruit en 1758.
Des vœux de reconstruction se font entendre dès 1789, qui paraissent notamment dans les cahiers de doléances du Tiers-Etat.
Un projet de pont voit le jour à l'initiative du préfet de l'Aveyron, M. d'Estourmel. Une commission chargée des moyens de son execution est ensuite réunie : elle comprend notamment Louis de Bonald (1754-1840), alors Maire de Millau, Paul Bonhomme, conseiller général, des membres de l'aristocratie locale, de Gualy et Sambucy de Sorgues ou encre un avocat, Boyer.
Les plans sont l'oeuvre de l'ingénieur de l'arrondissement Pierre Le Rouge, qui les réalise sous la direction de l'ingénieur en chef Raffeneau. Ils sont approuvés par ordonnance royale du 25 mars 1818. La construction débute dès juin 1818 et le pont est ouvert à la circulation en janvier 1821. Un droit de péage y est perçu jusqu'en 1875. Il est ensuite élargi une première fois en 1910-1911, puis en novembre 1937, afin que les véhicules puissent s'y croiser et les piétons circuler sur ses trottoirs.