Die Autobahnverbindung Dortmund-Gießen wurde 1957 beschlossen. Zwar hatte es bereits in den 1930er Jahren Vorüberlegungen für eine Strecke Hagen-Gießen gegeben, aber als erste große Autobahnstrecke nach dem 2. Weltkrieg beruhte sie nicht mehr auf Vorkriegs-Planungen und wurde vollständig neu entworfen. Zunächst war sie als Sauerlandlinie zur Erschließung der Sauer- und Siegerländer Industrieregionen sowie des Lahn-Dill-Gebiet mit dem Ruhrgebiet und Süddeutschland gedacht. Bald jedoch gewann sie zusätzliche überregionale Bedeutung als Entlastung für die "alte" Nord-Süd-Strecke Ruhrgebiet - Köln - Frankfurt.
Moderne Bautechnik erlaubte eine Streckenführung über die zahlreichen Täler mit einer Reihe von großen Talbrücken. Das gegebene Landschaftsrelief bedingt große Höhenunterschiede: So wird allein auf den 36 Kilometern zwischen Hagen und Meinerzhagen ein Höhenunterschied von 426 m bewältigt. Bedeutendere Täler in Nord-Süd-Richtung sind nicht vorhanden. Bei einer Autofahrt von Dortmund nach München wird bereits eine gute halbe Stunde nach dem Start die größte Höhe über dem Meeresspiegel auf dieser Route erreicht.
1963 wurde der erste Abschnitt zwischen Dortmund und dem Westhofener Kreuz freigegeben, wo die A45 mit der A1 verbunden ist. Weitere Abschnitte wurden in den Jahren 1967 und 1968 fertig gestellt. Die letzte Lücke im Landesgebiet wurde 1971 mit dem fast 50 Kilometer langen Stück zwischen Lüdenscheid und Freudenberg geschlossen. Im Jahr darauf war die A45 bis Gießen fertig.
Bis 1974 wurden auch die Erweiterungen im Raum Dortmund nach Norden fertig gestellt. Die A45 war damit nicht nur mehr mit der A1 verbunden (Westhofener Kreuz) und per Anschlusstelle an Dortmund angeknüpft (Dortmund-Süd), sondern auch mit der A44 (Kreuz Dortmund-Witten), der B1/A40 (Kreuz Dortmund-West), der A42 (Kreuz Castrop-Rauxel-Ost) und schließlich der A2 (Kreuz Dortmund-Nordwest) verbunden. Damit stellt die A45 einen bedeutenden Teil des Dortmunder Autobahnrings, zu dem noch die A2 und die A1 zählen.
1976 erhielt die A45 im Kreuz Olpe-Süd die Verbindung mit der A4 nach Köln und Aachen.
