Traseen over Filefjell ble allerede i 1793 etablert som hovedvei mellom Oslo og Bergen, den såkalte Bergenske Kongevei.[1]
Fra 1975 til europaveisystemet ble omorganisert i 1992 hadde veien betegnelsen europavei 68. Denne fulgte dagens trasé bare langs noen få strekninger. Fra Bergen sentrum til Indre Arna fulgte den den nåværende fylkesvei 580 via Haukeland frem til 1988 da Fløyfjelltunnelen ble åpnet. Mellom Trengereid og Vossevangen fulgte E68 dagens fylkesvei 49 og fylkesvei 79 via Norheimsund til Granvin og dagens riksvei 13 videre til Voss.[2] Før Lærdalstunnelen ble tatt i bruk i 2000 var ferjestrekningen Gudvangen-Revsnes del av veien. Den tidligere strekningen Revsnes-Lærdalsøyri har blitt privat/kommunal/fylkesvei.
Strekningen mellom Trengereid og Dale var tidligere del av riksvei 13, mellom Dale og Dalseid del av riksvei 569. Mellom Dalseid og Bolstadøyri var det ingen vegforbindelse, en ny veg mellom Dale og Evanger ble åpnet 1992. Fra Bolstadøyri gikk en fylkesveg til Evanger. Avsnittet Evanger – Bulken var opprinnelig riksvei 571, ved Bulken møtte den Rv13 fra Dale som gikk videre til Vossevangen.[2] Hovedveien Bergen-Voss ble lagt langs Bolstadfjorden i 1992 og noen jernbanetunneler (på Vossebanen) ute av bruk (etter åpning av Trollkonetunnelen) ble da utvidet til veitunneler. Tidligere gikk hovedveien gjennom Bergsdalen mellom Bulken og Dale.[3][4]
Stalheimtunnelen og Sivletunnelen ble åpnet i 1980, og eliminerte Stalheimskleivi, en problematisk veistrekning.
Gudvangatunnelen ble åpnet i 1991 og Flenjatunnelen i 1985, men ble brukt for europaveien først da Lærdalstunnelen åpnet i 2000. Flåm/Aurland hadde vanlig ferjesamband med Gudvangen til 1991, idag går det en turistbåt på strekningen.[5]
Lærdalstunnelen åpnet i 2000 etter 5 års byggearbeid, tunnelen ga helårs fergefri forbindelse. Før 2000 gikk E16 med ferge mellom Revsnes og Gudvangen.
Seltatunnelen (2003) forbi Galdane og Borgundtunnelen (2004) forbi Vindhella forkortet veien med 5 km og erstattet et vanskelig parti.
En helt ny veistrekning med nye broer og Tuftåstunnelen åpnet i 2008, forkortet E16 gjennom Lærdal og førte trafikken utenom bebyggelsen.
Stuvane-Seltun bru (4,3 km) var i 2013 ferdig utvidet til 8,5 m, ny Seltun bru og rasvoller.[6][7]
På den felles traseen med
Europavei 39 ble det i 2012 anlagt toplanskryss ved Nyborg i Åsane, og motorveien forlenget til Vågsbotn der E39 og E16 skilles.
En ny tunnel forbi Vossevangen, Vangstunnelen, ble åpnet i 2013 og førte gjennomgangstrafikken utenom sentrumsgatene.
Fra Borlaug i Lærdal kryss med riksvei 52 til Tyinkrysset ble større ombygging igangsatt høsten 2011. Borlaugstunnelen åpnet i juli 2014.[8]