Le groupe fût d'abord fondé en 1993 par un trio de producteurs américains, Butch Vig (qui a entre autres produit le légendaire "Nevermind" de Nirvana ainsi que "Gish" et "Siamese Dream" des Smashing Pumpkins), Duke Erikson et Steve Marker, tous originaires du Wisconsin. Leur principale activité était alors de rechercher des sonorités originales en combinant guitares et effets électroniques. Il leur fallait cependant une voix... Et ce fût tout à fait par hasard que Steve Marker, qui regardait une chaîne musicale cablée, remarqua un soir Shirley Manson dans le clip "Suffocate Me" d'Angelfish, un groupe britannique dont elle était alors la chanteuse et décidèrent de la contacter au printemps 1994. Le groupe ne devait être au départ qu'un projet informel, ne durer que le temps de quelques titres voire un album. Mais devant le succès que rencontra "Vow", leur premier titre, un véritable esprit de groupe se forma et donna naissance, l'année suivante (1995), à un premier album , qui rencontrera lui aussi un franc succès (plus de 6 millions d'albums vendus).

Depuis 1995, Garbage sortît une série de singles qui rencontrèrent un succès grandissant, pour culminer avec "Stupid Girl". Leur premier album, "Garbage", sortit un peu plus tard dans l'année. Il atteignit le top 20 aux États-Unis et le top 10 au Royaume-Uni. L'album s'inscrivait dans la continuité des essais musicaux de Butch Vig et de ses acolytes, mélangeant du rock sombre avec des rythmiques pop.

Le groupe travailla ensuite sur leur deuxième album pendant deux ans, durant lesquels Shirley Manson se fit connaître par les internautes comme étant une des premières artistes à tenir un blog. "Push It" sortit au printemps 1998, suivi par "Version 2.0", qui atteignit rapidement le statut de double disque d'or en France. Le son du groupe prit un virage vers le monde de la musique électronique, certaines des chansons comportant plus de 100 boucles et samples différents. Il fût aussi un des premiers albums à avoir été entièrement réalisés à l'aide d'un logiciel de création musicale. Un an plus tard, alors qu'ils viennent d'achever une tournée mondiale longue de 18 mois, on demanda au groupe d'interpréter le générique de "Le Monde ne suffit pas", le 19e film des aventures de James Bond.

Après s'être à nouveau longuement retirés dans leur studio de Madison, dans le Wisconsin, Garbage sortit "Beautifulgarbage" en 2001. Ce troisième album reste à ce jour le plus éclectique du groupe, chaque morceau explorant un univers musical particulier, bien que tous soient marqués par l'ambiguïté du titre de l'album (qui peut se traduire par "jolis détritus") : des mélodies pop sabordées par des paroles très sombres. "Beautifulgarbage" se classa au 3e rang des ventes en France lors de sa sortie mais fût bien moins considéré par la critique.

En 2003, le groupe apparaît sur la compilation "We're A Happy Family", sur laquelle divers groupes rendent hommage aux Ramones. Garbage y interprète "I Just Wanna Have Something To Do", qui avait déjà été jouée pendant la tournée "Beautifulgarbage".

Fin 2002, après une tournée mondiale longue de plus d'un an, le groupe entra dans une nouvelle période de silence pour enregistrer leur quatrième opus qui sortira environ deux ans et demi plus tard, intitulé "Bleed Like Me", en avril 2005. Les retards successifs de la sortie de cet album seraient dus à des tensions au sein du groupe en studio, voire à une séparation provisoire. Le clip du premier single, "Why Do You Love Me", semble être en partie autobiographique puisqu'on y voit les membres du groupe se quereller. "Bleed Like Me" sonnant comme un retour à un son plus brut et plus rock, les membres du groupe ont d'ailleurs déclaré qu'ils voulaient retrouver en studio l'énergie qu'ils ressentaient lors de leurs concerts, d'où une minimisation relative des effets électroniques pour mettre en avant le son des guitares. Des musiciens de renom dans le milieu du rock alternatif tels que Dave Grohl ou John 5 (Marilyn Manson) ont en partie participé à l'enregistrement de l'album ou de faces b et sûrement contribué à affirmer cette volonté de la part des musiciens.

En septembre 2005, le groupe a publié un communiqué dans lequel les membres annoncaient vouloir mettre l'aventure Garbage de côté le temps d'une pause d'une durée indéterminée, pour se reposer après une tournée exténuante et retrouver leurs proches. Rien n'est précis en ce qui concerne l'avenir du groupe, qui ne veut cependant pas parler de séparation définitive.