Overvejelserne om en bro over Vejle Fjord kom for alvor i gang, da Folketinget i sommeren 1965 vedtog Projekteringsloven for den jyske motorvej. Vejlefjordbroen var nødvendig for at gøre en ende på årtiers trafikproblemer, hvor hovedlandevejene A10, A13 og A18 efterhånden ledte omkring 40.000 køretøjer i døgnet gennem Vejles centrum. Som følge af anlægsstop blev det til adskillige udskydelser af hele bro- og motorvejsprojektet, men d. 11. august 1975 kunne amtsborgmester Erling Tiedemann sætte en sirene i gang, der markerede starten på byggeriet. Det var overdraget til et Vejlefjord-brokonsortium bestående af de danske entreprenørfirmaer Monberg & Thorsen A/S og A. Jespersen & Søn A/S samt det vesttyske Dyckerhoff & Widmann AG.
Fjordbunden bestod på brooverføringsstedet af et ca. 12 m tykt dyndlag og herunder et 12‑18 m tykt lag af sand og grus. Det krævede nedramning af 1.600 betonpæle med en længde på 30‑40 m som fundament for bropillerne. Vejlefjordbroen fik fire kørebaner; den 1.712 m lange betonbro bliver båret af 18 bropiller og har en gennemsejlingshøjde på 40 m. Den officielle indvielse fandt sted d. 1. juli 1980, hvorefter bilisterne endelig kunne slippe uden om Vejles centrum.
Med indvielsen af Vejlefjordbroen kom der ifølge Vejdirektoratets skøn dagligt omkring 16.000 færre biler gennem det centrale Vejle. Det løste dog ikke trafikproblemerne på længere sigt, for det markante fald i antallet af biler gennem midtbyen de første år efter indvielsen blev i 1990’erne afløst af en stadigt stigende kurve. Kort efter årtusindskiftet viste trafiktællinger, at broen nu blev passeret af over 50.000 køretøjer i døgnet.
I løbet af 2010’erne har Vejlefjordbroen udviklet sig til en trafikal flaskehals på E45. Den er Vestdanmarks mest befærdede bro og blev ifølge Vejdirektoratet på hverdagsdøgn i 2019 passeret af 89.900 køretøjer. I perioden 2008‑19 er trafikken steget med ca. 4 % om året og har dermed skabt stigende køer i de mest befærdede perioder.
Forsinkelserne har udviklet sig til et dagligt problem for erhvervslivet og de mange pendlere og er dermed også politisk blevet en omdiskuteret sag.
Blandt forslagene er udvidelser af E45 med flere spor. En anden plan er en ny midtjysk motorvej over Give til Hobro. Vejdirektoratets beregninger viser imidlertid, at den i 2030 kun vil medføre en aflastning af Vejlefjordbroen på mellem 3.000 og 10.000 køretøjer i døgnet. Et andet forslag er at styrke den kollektive trafik gennem en ny togbro over Vejle Fjord. Endelig indgår de østjyske trængselsproblemer i debatten om en bro over Kattegat fra Kalundborg via Samsø til Jylland.
Med de seneste års trafikudvikling vil Vejlefjordbroen i 2022 på hverdage blive passeret af over 100.000 køretøjer.
