Der Köhlbrand ist eine drei Kilometer lange Wasserstraße, die die Süder- mit der Norderelbe verbindet. Sie wurde als Folge der „Köhlbrandverträge“ (1869, 1896 und 1908) zwischen Hamburg und Preußen für den Schiffsverkehr reguliert und vertieft. Über sie konnten damals wie heute die großen Hafenterminals Harburgs angefahren werden. Als 1910 jedoch auch westlich des Köhlbrands die Waltershofer Häfen entstanden, musste eine Querung des Köhlbrands für Verteilerfahrzeuge geschaffen werden. Deshalb wurde ein regelmäßiger Fährverkehr eingeführt: Drei KfZ-Fähren konnten täglich zusammen etwa 6.000 Fahrzeuge über den Köhlbrand transportieren.
Mit der fortschreitenden Hafenerweiterung wuchsen die Hafenregionen links und rechts des Köhlbrands jedoch immer mehr zu einer logistischen Einheit zusammen. Die Köhlbrandfähren wurden dem höher werdenden Verkehrsaufkommen mit der Zeit nicht mehr gerecht. Die immer häufiger und länger werdenden Wartezeiten brachten Hamburg in Zugzwang – eine effizientere Möglichkeit zur Überquerung des Köhlbrands musste her. Diese Querung sollte den Verkehr zwischen den Hafenteilen beiderseits des Köhlbrands verbessern und, als Autobahnzubringer, die zentralen Hafenteile und das Industriegebiet Wilhelmsburg mit der A7 verbinden.
Auch damals schon wurde lange überlegt und berechnet, ob ein Tunnel oder eine Brücke die klügere Querungsvariante sei. 1968 fiel im Hamburger Senat schließlich die Entscheidung: Eine Brücke über den Köhlbrand sollte gebaut werden. Um das Vorhaben Gestalt werden zu lassen, wurde 1969 ein internationaler Ideenwettbewerb ausgeschrieben, an dem sich fünf Architektur- und Ingenieursbüros mit insgesamt acht Brückenentwürfen beteiligten. Der Architekt Egon Jux und der Bauingenieur Paul Boué konnten mit ihrem Vorschlag überzeugen und gewannen den Wettbewerb. Sie reichten einen Entwurf für eine elegante stählerne Schrägseilbrücke ein: 88 Stahlseile, befestigt an zwei kolossalen Pylonen von 130 Meter Höhe, sollten die Brücke über den Köhlbrand tragen. Ein so großes Bauwerk musste aber nicht nur schön aussehen, sondern auch einiges aushalten können. An der Technischen Universität in München wurde daher die Standfestigkeit der Brücke getestet. In einem Windkanal ließen die Wissenschaftler einen Orkan um das Modell der Köhlbrandbrücke toben und stellten fest: Der Brückenentwurf von Jux und Boué würde auch dem fürchterlichsten Hamburger Schietwetter standhalten.
Nun konnten die Planungen Fahrt aufnehmen. Schon nach zwei Jahren Bauzeit sollte die Köhlbrandbrücke stehen. Die Stadt Hamburg sah Baukosten in Höhe von 120 Millionen Mark vor, an denen sich die Bundesrepublik Deutschland mit 48 Prozent beteiligte.
Am 8. Mai 1970 begannen mit dem ersten Rammschlag die Bauarbeiten an der Köhlbrandbrücke. Der Bau der massiven Betonpfeiler, die einen Teil der Fahrbahn und die Pylone tragen sollten, stellte eine Herausforderung dar. Erst in 15 bis 20 Meter Tiefe ist der Boden fest genug, um das Gewicht der Brücke zu tragen. Deshalb sind die Pfeiler auf tief im Boden verankerten Ortbeton-Rammpfählen gegründet. Die schwierige Aufgabe, die 520 Meter lange, freischwebende Strombrücke (der Teil der Brücke, der sich tatsächlich über dem Wasser befindet) zu bauen, hatten die Planer schlau gelöst: Die Bauteile wurden größtenteils vorgefertigt, sodass die Brücke vor Ort Stück für Stück zusammengesetzt werden konnte. Zuerst mussten dafür die Pylone gebaut werden. Diese bestehen aus bis zu 700 Tonnen schweren Stahlbauteilen, die mithilfe eines Autokrans montiert wurden. Im nächsten Schritt wurde die in 34 Teilstücke zerlegte Brückenfahrbahn zusammengesetzt. Ein Schwimmkran brachte die Teile einzeln an die richtige Stelle, wo sie sofort verbaut und mit Stahlseilen an den Pylonen befestigt wurden. So wuchs die Brücke Stück für Stück von beiden Seiten über den Köhlbrand, ohne dass ein Gerüst nötig gewesen wäre.
Am 25. Oktober 1973 hängte der Schwimmkran „Magnus XII“ schließlich das letzte der insgesamt 34 Teilstücke der Brücke ein. Damit stand der Rohbau: Auf 58 Metern über dem Wasser wurde Richtfest gefeiert. Der damalige Wirtschaftssenator Helmut Kern überquerte an diesem Tag offiziell als erster zu Fuß den Köhlbrand. Doch bevor er den Weg über die Brücke antreten durfte, wurden ihm von einem Vorarbeiter gründlich die Schuhe poliert. Denn nach altem Brückenbauer-Aberglauben darf kein Schmutz von einer Seite der Brücke auf die andere getragen werden.
Ende September 1974 war es dann endlich soweit: Die Bauarbeiten an der Köhlbrandbrücke waren abgeschlossen. Aus den ursprünglich geplanten zwei Jahren Bauzeit waren viereinhalb geworden. Auch das errechnete Budget konnte nicht ganz eingehalten werden. Statt den geplanten 120 Millionen Mark wurden insgesamt 160 Millionen Mark für den Bau ausgegeben. Dafür konnte sich die fertiggestellte Köhlbrandbrücke sehen lassen. 81.000 Kubikmeter Beton und 12.700 Tonnen Stahl wurden insgesamt in den 75 Pfeilern, zwei Pylonen und 88 Stahlseilen der Brücke verbaut. Sie schien mit ihrer schwebenden, schwungvollen Ästhetik und ihrer majestätischen Größe vor allem die Lokalpresse zu überzeugen. Diese bezeichnete die Köhlbrandbrücke als „Triumphbogen“ oder als „elegant gekurvte Wespentaille des Hamburger Hafens“. Auch das Fachpublikum war von der anmutigen Leichtigkeit des Bauwerks begeistert. 1975 erhielten Egon Jux und Paul Boué für ihre Köhlbrandbrücke den Deutschen Stahlbaupreis.
Die neue Köhlbrandbrücke hatte aber für manche Hamburger Bürgerinnen und Bürger auch Schattenseiten mit sich gebracht: Für den Bau der Brücke musste der kleine Wilhelmsburger Stadtteil Neuhof weichen. 300 Familien wurden umgesiedelt und mussten ihr Zuhause am Köhlbrand hinter sich lassen.
Bevor die neue Köhlbrandbrücke für den Autoverkehr geöffnet wurde, feierte die Stadt Hamburg ein gebührendes Eröffnungsfest. Vom 20. bis 22. September 1974 war die Brücke ausschließlich für Fußgängerinnen und Fußgänger geöffnet. Der damalige Bundespräsident Walter Scheel reiste aus Bonn an, um die Brücke mit einer Rede und dem obligatorischen Scherenschnitt zu eröffnen. Kaum hatte der Präsident den Satz „Nu denn, latschen wir mal nieber“ ausgesprochen, stürmten hunderttausende Besucherinnen und Besucher die vier Kilometer lange Fahrbahn und überquerten den Köhlbrand zu Fuß. Als Begleitprogramm war einiges geboten: Nach dem Brückenmarsch verteilte der Senat Erinnerungsmedaillen, ein Sensationsdarsteller umkreiste die Brücke in luftiger Höhe auf einem Fahrrad, das von einem Hubschrauber getragen wurde, und Fahrgeschäfte und Essen/Getränke-Buden verwandelten die Eröffnungsfeier in ein regelrechtes Volksfest. Für das Eröffnungswochenende wurde sogar extra ein Sonderzug eingerichtet, der Besucherinnen und Besucher über die Gleise der Hafenbahn vom Hauptbahnhof zur Köhlbrandbrücke brachte.
Am 23. September 1974 um sechs Uhr morgens wurde die Brücke schließlich für den Autoverkehr geöffnet. Anfangs kam es noch öfter zu Stau, vor allem weil am Wochenende gerne Touristen mit dem Auto zur Brückenbesichtigung fuhren. Mit der Zeit pendelte sich der Verkehr jedoch ein.
