Gadens navn har forbindelse med flådeværftet, der indtil midten af 1800-tallet lå på øen Bremerholm.
Ved Bremerholm lå de såkaldte Skipperboder, som på kong Christian den 4.’s tid blev opført som boliger for kongens skibsfolk (”Holmens faste stok”). De var bygget fra 1614 og frem, men blev nedlagt igen, da kongen omkring 1630 flyttede boligerne udenfor selve byen, og dermed opstod kvarteret Nyboder.
Tidligere lå her Københavns Slots have, der dog blev nedlagt, da Rosenborg Slot blev bygget og haven anlagt der i stedet for.
Bremerholm blev i 1930’erne ført igennem fra Østergade til Holmens Kanal, og dermed forsvandt en række smågader, blandt andet den berygtede Holmensgade.
Mellem Laksegade og Holmens Kanal gik tidligere Hummergade, som nu er nedlagt (Se nærmere om gaden i artiklen om Laksegade). Ved Bremerholm 35 er et indhak i husrækken, som viser, hvor gaden gik (billedet herover).
Mellem Lille Kongensgade og Østergade lå tidligere en lille gade, der hed Integade. I dag er gaden væk og i stedet opstået et lille torv, der uofficielt kaldes Magasins Torv.