Alors qu’une compétition internationale est lancée entre cinq familles de solutions, en janvier 1995, le viaduc de contournement est déclaré d’Utilité Publique. A l’époque, on parle d’un achèvement en 2001… Le projet de viaduc Multihaubané défendu par l’architecte anglais Norman Foster l’emporte.
Reste à passer à la concrétisation. L’Etat toujours impécunieux se voit mal sortir les deux milliards nécessaires.
Alors ? On recours alors à un montage redevenu à la mode dans le BTP, la concession où un groupe privé construit puis exploite l’ouvrage durant une durée fixée à l’avance pour se rembourser.
C’est la solution Eurotunnel (pas toujours très heureuse pour les actionnaires...) En fait, sur une vision millénaire, un pont à péage, cela n'a rien de très nouveau en Aveyron. Tous ses jolis ponts médiévaux étaient l'objet d'un péage et de revenu pour le seigneur local. De là, à dire qu'Eiffage est le nouveau seigneur de Millau, il y a un pont....à ne pas franchir.

Les fils spirituels d’Eiffel
En octobre 2001, le groupe Eiffage est choisi. Ses hommes ont défendu une solution où l’acier prédomine notamment avec le tablier. Leur père spirituel, Gustave Eiffel, ingénieur d’un autre viaduc bien connu, celui de Garabit, doit apprécier cette confiance renouvelée dans l’acier. On s’en tient à une livraison de l’ouvrage pour 2004, date politique, mais mieux vaut tabler sur une mise en service début 2005. Le concessionnaire n’a pas de temps à perdre car qui dit retard dans la mise en service, dit manque à gagner.