Rozhodnutí o stavbě padlo už v roce 1963, usnesení vlády bylo několikrát aktualizováno. Stavba byla zahájena stavbou mostu v Berouně v roce 1976. Dokončení stavby bylo plánováno v roce 2000. Ze začátku probíhala stavba velice pomalu, první otevřený úsek bylo 9 km dálnice z Prahy-Zličína do Loděnice v roce 1982, poté stavba postupovala tempem cca 2–3 km ročně. V roce 1989 byl zprovozněn úsek do Bavoryně (vesnice cca 1 km západně od Zdic) a délka zprovozněného úseku dálnice tak dosáhla 29 km. Termín dokončení celé dálnice byl posunut na rok 2010. Po roce 1989 se stala dálnice D5 prioritní stavbou, která měla zajistit zlepšení dopravního spojení se západní Evropou. Rychlost stavby se zněkolikanásobila. Již v roce 1995 byl otevřen celý úsek až k Ejpovicím, odkud vede čtyřpruhová komunikace na východní okraj Plzně. Usnesením vlády ze dne 24. května1995 č. 304 bylo schváleno propojení české dálnice D5 a německé dálnice A6 na společných státních hranicích výstavbou hraničního mostu. Toto propojení se stalo realitou v roce 1997, kdy byl dokončen celý úsek z Plzně až do pohraničního městečka Waidhaus v Německu.
Jediným nezprovozněným úsekem dálnice byla dlouhou dobu část obchvatu města Plzně. Ten se stal velice problematickým úsekem dálnice. Jeho projednávání trvalo 15 let a jedná se tak o nejsložitější kauzu porevoluční historie správních řízení. Během projednávání došlo k čtyřem změnám na pozici ministra životního prostředí (a tím i změnám v pohledu na výstavbu), silnou roli zde sehrály i lobbistické skupiny (tzv. zelená a betonová lobby).
Původně bylo rozhodnuto roku 1988 o severním obchvatu Plzně. Z důvodu odporu chatařů v oblasti západně od Plzně a vodohospodářů (dálnice měla přetínat vodní nádrž Hracholusky) se začala zvažovat jižní varianta. Zde už od počátku proti sobě stály dvě varianty, tzv. varianta S a varianta K. Vláda ČR z podnětu města Plzně schválila 20. prosince 1991 upravenou variantu K (tzv. KU) jakožto prioritní variantu výstavby. V následujícím správním řízení vyhodnotil posudek EIA variantu KU jako příznivou, a to v optimalizované úpravě jako tzv. KU0. Vláda, která se mezitím vyměnila, použila ovšem jiný posudek a schválila v roce 1994 upravenou variantu S, tzv. SUK. Okresní úřad Plzeň-jih pak vyhověl námitkám občanských sdružení a posunul vedení dálnice jižně od vrchu Valík, aby nedošlo tak k výraznému zásahu do lesního komplexu a snížil se vliv stavby na krajinný ráz – tzv. varianta SUK1. Ministr životního prostředí František Benda ovšem toto rozhodnutí okresního úřadu označil za rozporné vůči nařízení vlády z roku 1994, a tak vydal souhlas se zásahem do významného krajinného prvku Valík v původně navržené trase SUK. Poté následoval koloběh neúspěšných odvolání různých účastníků řízení (obce, občané, občanská sdružení), během nějž byla trasa upravena o tunel v nejhlubší části zářezu.
Teprve v roce 1998 zrušil ministr životního prostředí (tentokrát Martin Bursík) souhlas se zásahem do krajinného prvku, neboť na tuto variantu nebyla provedena EIA a byl tak porušen zákon. Spor se tak vrátil do samotného počátku. Po dalších 4 letech jednání, během nichž byla stavba obchvatu rozdělena na tři dílčí stavby, západní a východní nekonfliktní část byla schválena, byla zde zahájena stavba a střední nadále procházela dalšími řízeními, byla dálnice schválena opět ve variantě SUK2. Tunel pod vrchem Valík je dlouhý 380 m a výška průjezdního profilu je 5,35 m.
Otevření první části obchvatu 15.12.2003 bylo velkolepou oslavou za účasti hejtmana a primátora. Hejtman Plzeňského kraje označil dálnici D5 za nejdůležitější stavbu v kraji po roce 1989. Oslava i následně média prezentovala obchvat nesprávně jako dokončený (nikoliv jen zčásti dokončený), a tak v prvních měsících došlo v nedokončených úsecích k několika velmi vážným dopravním nehodám.