12 ноября 1996 года группа выпускает сборник видеоклипов Garbage Video. 14 ноября Garbage получили награду «MTV Europe Music Awards» в категории «Прорыв года». Ремикс песни «#1 Crush», сделанный Нелли Хупером, прозвучал в фильме База Лурмана Ромео + Джульетта, а также получил номинацию на «MTV Movie Awards». Кроме того, песня «As Heaven is Wide» вошла в саундтрек к компьютерной игре Gran Turismo для игровой приставки PlayStation. В феврале 1997 года группа получиа номинацию на премию «Грэмми» в категориях «Лучший новый исполнитель», «Лучшее вокальное рок-исполнение дуэтом или группой» и «Лучшая рок-песня» за композицию «Stupid Girl».

Version 2.0 (1997—1999)

Далее последовал долгий путь новых экспериментов. В марте 1997 года Garbage перехали в Вашингтон для записи новой пластинки. Участники группы были весьма взыскательны к качеству своего музыкального материала, и поэтому пауза между первым и вторым альбомами составила почти три года. Рабочим названием пластинки было Sad Alcoholic Clowns. Все песни записывались при помощи 48-трековой цифровой системы прямо на жёсткий диск с использованием программы Pro Tools. Когда часть материала была готова, группа перебралась в Мэдисон, где в Smart Studios музыканты продолжили работу над диском. Ударные партии к некоторым композициям записывались в помещении заброшенной конфетной фабрики Мэдисона, из-за чего в местное отделение полиции неоднократно поступали жалобы по поводу шума. Бас-партии на альбоме исполнены концертным участником группы Daniel Shulman.

15 февраля 1998 года работа над альбомом была окончена. Также музыканты объявили официальное название новой пластинки — Version 2.0. Известно, что это название было предложено Ширли Мэнсон. В марте 1998 с альбома выходит первый сингл «Push It», который сразу же возглавил чарт Великобритании. Сюрреалистический видеоклип на эту песню приобрёл большую популярность и часто транслировался на MTV. По поводу текста песни и необычного клипа Ширли Мэнсон сказала: «„В Push It“ идёт речь о шизофрении, которая появляется при попытке усмирить свои желания и своих личных демонов». Музыкальное видео было положительно встречено критиками и получило тринадцать номинаций на премии «MTV Video Music Awards», «MTV Europe Music Awards» и MVPA Music Video Awards.

11 мая 1998 года свет увидел второй студийный альбом Garbage Version 2.0. Диск дебютировал на 1-й строчке британского чарта и на 13-й строчке Billboard 200. Альбом получил положительные отзывы от музыкальных критиков и был удостоен золотой сертификации в Великобритании, Франции, Бельгии, Новой Зеландии, и платиновой сертификации в Европе, Испании, Ирландии, Сингапуре, Канаде и США.

15 мая 1998 в поддержку альбома стартовал концертный тур Version 2.0 World Tour, который продлился до ноября 1999 года. Тур охватывал Северную Америку, Европу, Азию, Южную Африку и Австралию. Кроме того, группа выступила на различных рок-фестивалях и радио-шоу, а также на разогреве у Red Hot Chili Peppers и Аланис Мориссетт. На разогреве у самих Garbage выступали такие известные группы, как The Crystal Method, Placebo, Moloko, Girls Against Boys и другие. Во время тура Garbage впервые выступили в России. Концерты в Париже и Санкт-Петербурге были сняты и показаны на каналах MTV Europe и MTV Россия.

1 октября 1998 Garbage получили номинацию на премию «MTV Europe Music Awards» в категориях «Лучшая группа», «Лучшее рок-выступление» и «Лучшее видео» за клип «Push It». В январе 1999 года Garbage были номинированы на премию «Грэмми» в категориях «Лучший альбом года» и «Лучший рок-альбом», а в сентябре группа была удостоена премии «MTV Video Music Awards» в категории «Лучшие спецэффекты» клип на песню Special. Позднее, за композицию Special, Garbage были номинированы на премию «Грэмми» в категориях «Лучшая рок-песня» и «Лучшее вокальное рок-исполнение дуэтом или группой».