Vejen blev anlagt i slutningen af 1600-tallet, og førte fra byen til Københavns Toldbod, der lå mellem Nyhavn og Sankt Annæ Plads.
I 1700-tallet blev gaden kaldt for “den realeste (dvs. den mest lige) og længste i staden”.
Senere flyttede toldboden længere nordpå til Nordre Toldbod og gaden kom på strækningen nord for Sankt Annæ Plads indtil 1940 Ny Toldbodgade, hvor den fra starten bestod af en dæmning.
I første halvdel af 1700-tallet lå en række tømmerpladser langs Toldbodgade ud mod havnen. De blev senere i århundrede afløst af pakhuse, der kom til at dominere gaden. De ligger alle ud mod Larsens Plads, som er navnet på kajgaden langs havnen.
Pakhusene ligger på langs af kajerne, fordi der ikke her var moler og anløbsbroer som på Christianshavn, hvor de ligger på tværs.
Endnu ligger flere af de gamle pakhuse her, f.eks. “Det Blå Pakhus” (billedet herover), der er tegnet af hofbygmester Casper Frederik Harsdorff (1735-1799) og er bygget for Østersøisk-guinesisk Handelsselskab omkring 1780, på samme tid som Vestindisk Pakhus, der ligger lidt længere mod nord.
Navnet skyldes enten en tidligere blåsort pudsning af facaden eller at huset har haft blå skodder for vinduerne. Huset var i brug helt indtil 1960’erne, senest dog som korntørringsmagasin. I dag er pakhuset indrettet til beboelse og rummer ca. 40 lejligheder.
Længst mod syd, ved Sankt Annæ Plads, ligger to pakhuse ligeledes opført for Østersøisk-guineisk Handelsselskab.
De er opført i 1787 og tegnet af ingeniørofficer H.E. Peymann. I 1885 blev de bygget sammen og brugt af rederiet DFDS som korntørringsmagasin. Fra 1973 er pakhusene indrettet til Hotel Admiral (herover).
Toldbodgade 71-89 er det såkaldte “engelske rækkehuse”, som efter engelsk tradition blev bygget i med lejligheder i tre etager. Husene er tegnet af arkitekten Vilhelm Tvede (1826-1891) og opført af Det Classenske Fideicommis omkring 1874.