Gaden er opkaldt efter den belgiske hovedstad Bruxelles, som på dansk tidligere blev kaldt Bryssel.
Inspirationen kom formentlig fra den nærliggende Belgiensgade. Kvarteret syd og øst for har en del gader med navne hentet fra europæiske lande og storbyer.
Brysselsgade hed indtil 1934 Oliegreensgade efter en ejendom, der lå her. Den blev i begyndelsen af 1800-tallet købt af Jacob Holm, der på den jord opførte sit store rebslageri (se nærmere under Jacob Holms Gade og Reberbanegade).