Диск получил неоднозначную реакцию критиков и фанатов группы[3], но несмотря на это Beautiful Garbage дебютировал на первом месте Billboard 200[4], возглавил чарты Австралии[5] и попал в «Топ-10 альбомов года» журнала Rolling Stone[6].
Работа над Beautiful Garbage началась в сентябре1999 года, когда Garbage собрались в студии во время мирового турне в поддержку альбома Version 2.0[7]. Группа записала два трека, «Silence Is Golden» и «Til the Day I Die», которые музыканты рассматривали как возможные би-сайды к будущим синглам[8]. В конечном же итоге эти две композиции были включены в новый альбом.
В начале 2000 года американский дистрибьютор Garbage Almo Sounds[англ.] был продан Universal Music Group[9] и группа решила уйти с лейбла, но Universal Music был против этого, и дело закончилось судом, вставшим на сторону музыкантов. Garbage подписали контракт с Interscope Records и в апреле 2000 года в Smart Studios[англ.] приступили к работе над третьим альбомом. При работе над материалом группа ещё больше экспериментировала со звуком, тем самым стараясь отойти от традиционного рок-звучания. Музыканты использовали большое количество различных средств обработки звука и клавишных инструментов[10]. По словам участников группы, они стремились создать как можно более насыщенное звучание. Во время записи пластинки к Garbage присоединился концертный участник группы Дэниел Шульман[англ.], исполнивший бас-партии в композициях «Androgyny» и «Nobody Loves You»[11], и Мэтт Чемберлен[англ.], который сыграл на барабанах в Can’t Cry These Tears и Cup of Coffee[12]. В мае2001 года запись альбома была окончена[13]. Позднее в Нью-Йорке прошёл процесс микширования пластинки. Название альбома выбиралось при участии фанатов, среди которых на официальном сайте группы был объявлен конкурс на лучший вариант (окончательное название — слова из песни Hole «Celebrity Skin» 1998 года).
В ноябре 2001 года был проведён конкурс на лучший ремикс песни «Androgyny». Участники конкурса могли загрузить свою работу на специально созданный веб-сайт www.acidgarbage.com. Победитель получил лицензионные копии музыкальных программ Sonic Foundry: ACID Pro 3.0, Sound Forge 5.0 и Vegas Audio 2.0.