1929 war die bis dahin eigenständige Stadt Hamborn mit Duisburg vereinigt worden (bis 1935 Duisburg-Hamborn), auf Grund des zwischen ihnen befindlichen Ruhrorter Hafens gab es aber kaum Verkehrsverbindungen. Schon lange davor hatte es Planungen gegeben, diesen Missstand zu beheben.
Bereits 1928 entstand der Plan einer kombinierten Straßen- und Straßenbahnverbindung zwischen der Duisburger Innenstadt und Hamborn. Zusammen mit dem Neubau des Duisburger Hauptbahnhofs 1934 wurde der Bahnhofsvorplatz auf zwei Verkehrsebenen angelegt. Zeitgleich wurde im Verlauf der Königstraße eine Brücke über die zukünftige Trasse errichtet, von der aus eine Rampe für die Straßenbahn zur Straßenbahnhaltestelle auf der unteren Ebene errichtet wurde (siehe auch Geschichte des U-Bahnhofs Duisburg Hauptbahnhof).
Durch den Zweiten Weltkrieg wurde der Weiterbau verzögert und aufgrund einer zu Gunsten des Individualverkehrs geänderten Verkehrspolitik der 1950er Jahre wurde die ursprüngliche Planung zu Gunsten einer reinen Stadtschnellstraße aufgegeben, ab 1952 stand die Nord-Süd-Straße im Duisburger Wirtschaftsplan.
Zunächst wurde Richtung Süden gebaut. Das erste Teilstück zwischen Landfermannstraße und Koloniestraße wurde am 24. April 1955 begonnen und am 27. Mai 1957 eingeweiht. Am 13. Juli 1959 folgte der nächste Abschnitt bis Grunewald. Obwohl noch recht kurz ist dies damit die erste Stadtautobahn (West-)Deutschlands.
Der Bau Richtung Norden erwies sich nicht nur auf Grund der zu überbrückenden Hafenanlagen als ungleich schwieriger, die Trassierung durch ein Gebiet mit Bergschäden erschwerte zusätzlich das Vorankommen. So wurde die Rampe von der Landfermannstraße über den östlichen Innenhafen, die Duisburger Hafenbahn und die damalige Bundesautobahn 2 (heute Bundesautobahn 40) zum Ruhrdeich erst am 19. Juni 1962 vollendet.
Im Anschluss daran folgt Europas damals längste Straßenbrücke (1.824 m), die die Ruhr, den Rhein-Herne-Kanal und die Becken des Ruhrorter Hafens überbrücken musste. Angesichts dieser enormen Entfernung gab man ihr als Zeichen der Verbundenheit mit den Einwohnern von Berlin den Namen Berliner Brücke, was auch durch die Doppelplastik „Begegnungen“ der Berliner Künstlerin Ursula Hanke-Förster am südlichen Brückenende ausgedrückt wird.[1] Diese zeigt zwei stilisierte Gruppen von Menschen, welche sich – durch die neugebaute Straße getrennt – gegenseitig zuwinken.
Von der Berliner Brücke in Meiderich aus verläuft die Nord-Süd-Straße in Hochlage durch dicht besiedeltes Gebiet. Dieser am 7. Oktober 1969 vollendete Streckenabschnitt bis zur Warbruckstraße in Marxloh fällt bis heute auf durch seine enge und kurvige Trassierung.
Auch Richtung Süden muss ein aufwändiger Brückenbau realisiert werden, da die verkehrsreiche Kreuzung am Grunewald bereits in erster Ebene von der Bahnstrecke Köln–Duisburg und in zweiter Ebene von der Bahnstrecke Mönchengladbach–Duisburg und der Bahnstrecke Osterath–Dortmund Süd überquert wird. Der Abschnitt bis zur Wacholderstraße in Wanheimerort inklusive der 1.016 m langen Grunewald-Brücke wurde am 29. Oktober 1975 eröffnet. Am 1. April 1977 folgt der letzte unter der Regie der Stadt Duisburg errichtete Abschnitt bis zur Sittardsberger Allee in Buchholz.
Die A 59 in Höhe des Duisburger Hbf in Richtung Süden
Der nördliche Teil der Nord-Süd-Straße vom (Autobahn-)Kreuz Duisburg am Ruhrdeich bis zum nördlichen Ausbauende wurde am 1. Januar 1979 zur Bundesautobahn 59 erhoben, zwei Jahre später am 1. Januar 1981 folgte dann der Rest bis zum südlichen Ausbauende.
Mit dem Übergang in den Besitz und die Trägerschaft des Landschaftsverbandes Rheinland endete damit die offizielle Bezeichnung als „Nord-Süd-Straße“, allerdings hält sich diese wie auch „Nord-Süd-Achse“ in der Umgangssprache der Duisburger Bevölkerung bis heute.
