Brunnsgatan österut sedd från Malmskillnadsgatan, 1966.
Den västra delen av Brunnsgatan som idag sträcker sig mellan Regeringsgatan och Malmskillnadsgatan hette tidigare Svarvargatan (1646: Swarffwaregathun). Namnet härrörde troligen från svarvaren Jöns Hindrichsson som hade en gård i nuvarande kvarteret Polacken. Efter 1670-talet dominerar namnet Brunnsgränden.
Östra delen mellan Regeringsgatan och Norrlandsgatan kallades Sågaregatan (1648: Sågare gathun) samt Stakens gata (1667: Stakens gatu). Nuvarande namnform för hela sträckningen användes efter 1857.
Brunnen som gav Brunnsgränden och senare Brunnsgatan sitt namn låg nedanför Sankt Johannes kyrka. Brunnen nyttjades sedan ”urminnes tider” av de boende i omgivningen och blev 1762 rensad, stensatt och inhägnat av ett järngaller. Hundra år senare hade brunnens vatten dålig kvalitet och karakteriserades som ”rent vatten som sattes i beröring med gödsel eller gödslad jord”.
