Gustav Henriksen var Den norske Amerikalinjes (NAL) første administrerende direktør og gjorde en betydelig innsats i NALs vanskelige etableringsperiode etter starten 1910. Gjennom 28 år arbeidet han Amerikalinjen frem til å bli et nasjonalt symbol, et viktig element i norsk nasjonsbygging og et uttrykk for de tette bånd mellom Norge og Amerika.
Gustav Henriksen var bare 14 år da faren døde. Familien flyttet til Kristiania, der han tok handelsgymnaset. 1889 ble han ansatt i D/S A/S Otto Thoresens Linje, og han hadde lang erfaring med linjefart da han 1910 ble medlem av et utvalg som utarbeidet planer for en skipslinje som skulle drive frakt- og passasjerfart mellom Norge og USA. Året etter ble han ansatt som administrerende direktør for den nye amerikalinjen.
Da Henriksen tiltrådte, var NAL i en prekær situasjon. Styremedlemmer trakk seg, skipsfartsnæringens mektigste menn tvilte på foretaket, og økonomiske problemer tårnet seg opp. Henriksen fikk til en finansiell konsolidering og bygde opp en landsdekkende organisasjon. Passasjerskipene Kristianiafjord og Bergensfjord ble kontrahert i Storbritannia, og 1913 ble de satt inn i linjen på USA. Da den første verdenskrig brøt ut året etter, førte tonnasjeetterspørselen til at NAL også satset på rene lastebåter.
Amerikalinjen fikk stor betydning for forsyningen til Norge, men krigen skapte også vansker. I januar 1915 erklærte tyskerne området rundt De britiske øyer for krigssone, og i juli ble Trondhjemsfjord torpedert på vei til Kirkwall med britisk prisemannskap om bord. I strid med britiske instrukser lot NAL sine passasjerskip seile nordenom Shetland. I februar 1917 erklærte tyskerne uinnskrenket ubåtkrig, og NALs passasjertrafikk ble drastisk redusert. Da USA kom med i krigen i april, ble Amerikalinjen lammet, og om sommeren totalforliste Kristianiafjord. NAL hadde riktignok et nytt passasjerskip under bygging i Storbritannia, men britene nektet å gi slipp på skipet. Først etter harde forhandlinger ble Stavangerfjord – Skandinavias største skip – formelt overlevert 25. april 1918. Noen dager senere la det ut på sin første tur til New York.
1918 ble Henriksen visepresident i Norges Rederforbund, som spilte en sentral rolle i håndhevelsen av norsk nøytralitetspolitikk. Da Tyskland fristet med en avtale om leidebrev, påla regjeringen forbundet å forhandle av hensyn til forsyningssituasjonen. En delegasjon under ledelse av Gustav Henriksen ble sendt til Berlin, og avtalen kom i havn. Etter krigen viste det seg at NAL var den eneste av de tre skandinaviske amerikalinjene som hadde klart å opprettholde regelmessige seilinger under hele krigen.
NAL hadde store inntekter under krigen, men Gustav Henriksen og direksjonen stod for en forsiktig utbyttepolitikk. Det var “av den aller største viktighet” for et selskap som NAL “å stå sterkest mulig rustet for det tilbakeslag og den kamp” som man visste ville komme. NAL var et fristende spekulasjonsobjekt, og 1919 planla et konsortium å kjøpe opp halvparten av aksjene i NAL for deretter å skrive opp aksjekapitalen og utstede friaksjer. For å avverge kuppforsøket truet Henriksen med å gå av. Debatten som fulgte, viste at NAL ble oppfattet som en nasjonal institusjon snarere enn et forretningsforetak.
Henriksen var president i Norges Rederforbund 1921–24, da rederinæringen ble rammet av et kraftig økonomisk tilbakeslag og mange selskaper fikk dødsstøtet. NAL klarte seg etter omstendighetene godt, bl.a. fordi selskapet utvidet sitt virkeområde. Nye linjer ble etablert, og man satset for en tid på tankfart. Som følge av krigen falt den tyske linjekonkurransen midlertidig bort, men høsten 1929 kom børskrakket i USA, og verdensøkonomien gikk inn i en kraftig og langvarig nedgangsperiode. Dessuten ble utvandringen til USA og Canada kraftig redusert. Denne gangen var mulighetene for ekspansjon på andre områder begrensede, og NAL måtte la skip gå i opplag. Øst-Afrikalinjen var imidlertid et lyspunkt, og Henriksens utvidelse av engasjementet der ble vellykket.
Passasjerskipene Bergensfjord og Stavangerfjord var rederiets ansikt utad. Den stramme økonomien tillot ikke at de ble skiftet ut, selv om de ikke tilfredsstilte tidens krav. I stedet ble de modernisert. Samtidig prøvde man å bedre den økonomiske situasjon ved å supplere med ulike cruisetilbud. 1935 innså Henriksen at det var nødvendig å skaffe et nytt skip til erstatning for Bergensfjord. Kontrakt ble inngått med et tysk verft, og 4. juni 1938, nøyaktig 25 år etter Kristianiafjords første avgang fra Kristiania, la Oslofjord ut på sin jomfrutur. Skipet var den norske handelsflåtes flaggskip og en ambassadør for landet. I interiører og kunstnerisk utsmykning skulle det vise “vår egenart, vår smak og vår kultur”.
1938 ble Henriksen utnevnt til kommandør av St. Olavs Orden for sine fortjenester for norsk skipsfart. Henriksen hadde da vært syk i flere år, men hadde hele tiden ledet selskapet “med aldri sviktende interesse og dyktighet”. Ved hans død 1939 var NAL med vel 100 000 brutto registertonn landets 7. største rederi.