Gaden hed oprindeligt Adelstredet, men er opkaldt efter et såkaldt boldhus, som var en slags gymnastik- og boldspilshus for de kongelige på Københavns Slot.
Boldhuset blev opført på initiativ af kong Christian den 4. i 1597 i den tidligere kongelige urtehave på Bremerholm. Det var formentlig et langt og lavt hus med hvælvet tag, og lå omtrent hvor Forsvarsministeriets bygning langs Ved Stranden ligger i dag.
Kongen brugte selv boldhuset til fornøjelser og spil. Man spillede en slags langbold, og spillet blev ledet af en “boldmester”.
Ved boldhuset lå den kongelige urtehave, som også blev brugt til f.eks. ringridning.
Engang efter 1814 skule området bruges til at opføre skipperboder – dvs. boliger for Flådens mandskab (der senere blev til Nyboder) – så huset blev flyttet til Slotsholmen, hvor et nyt boldhus blev opført omkring den nuværende Slotsholmsgade.
Boldhusgade blev anlagt 1625 og blev betegnet som et stræde der gik fra “stranden og op udi kongens ny boder”. Det gamle boldhus nævnes dog endnu i midten af 1600-årene, så det er uvist, hvornår det blev revet ned.
Gaden har givet navn til Boldhus Teatret, der åbnede i 1967. Teatret lå dog i Admiralgade.