Som en del af planen i 1860’erne for opførelsen af det nye, mondæne kvarter på Gammelholm, var også en gade langs havnen.
I det første forslag til Gammelholms bebyggelse, udarbejdet af arkitekten Gustav Friedrich Hetsch (1788-1864), hed det der langs havnen kunne anlægges en “med træer beplantet spadserergang”, som kunne forbinde Nyhavn med kvarteret omkring Børsen og Holmens Kirke.
Kajen her var tiltænkt dampskibene, der endnu blev betragtet som mere moderne og lidt finere end sejlskibene, så de fik én af de fornemme pladser.
Havnegade blev anløbssted for skibe i rutefart til såvel Malmö som Bornholm. Det var også herfra, at en del skibe med udvandrere, der søgte lykken i fremmede lande, afgik.
Bebyggelsen langs havnen blev nok lidt finere end i Gammelholms øvrige gader.
Selv om der generelt blev bygget tæt her, tillod man sig alligevel et villabyggeri (herover) på hjørnet af Havnegade og Tordenskjoldsgade, tegnet af Johan Daniel Herholdt. Huset var opført som bolig for vekselereren Martin Levin, men blev fra 1922 hovedsæde for De Danske Spritfabrikker.
Én af de første bygninger på Gammelholm var navigationsskolen, der ligger Havnegade 23 (tegningen herover). Den var tegnet i 1865 af arkitekten Ferdinand Meldahl (1828-1908), som også lavede bebyggelsesplanen for hele kvarteret.
Selv om Navigationsskolen i det ydre fremstod som en italiensk renæissancebygning, var den ganske moderne indrettet. Det var f.eks. et af de første steder i København, hvor der var indlagt centralvarme.
Forbilledet for navigationsskolens bygning var et palads i Venedig. Men arkitekten tilføjede små runde vinduer med røde og grønne glas, som en reference til sømandsuddannelsens centrale pensum om farverne for styrbord og bagbord.
Navigationsskolen flyttede i 1891 til andre lokaliteter på Gammelholm, men fik i 1954 helt nye bygninger på Jagtvej på Nørrebro. I dag bruges bygningen af et forsikringsselskab.
I rækken af beboelsesejendomme langs havnen, blev der plads til et pakhus, som blev opført 1865. Det blev i 1917 overtaget af Nordisk Frøkontor, hvis navn stadig står på facaden. Bygningen er fredet, som én af de forholdsvis få, bevarede pakhusbygninger i Københavns Havn, og ses med gavlen mod havnen.
I 1937 blev der opført et kombineret toldkammer og færgeterminal ved havnekajen (herover). Den blev brugt i forbindelse med færgerne til Sverige, som udgik herfra.
Bygningen var tegnet af arkitekten Kristoffer Varming (1861-1936), og blev først indviet i 1937 efter hans død. Rederiet Scandlines brugte terminalen indtil 2002, og siden har den været restaurant.