The band started in Hamilton in 1994. Its four members - Paul Smith (guitar/vocals), Brent Soper (casiotone/drum machine), Dominic Worthington (vocals) and Kyle Smith (guitar) - were all friends who had been involved in various performance events and were associated with Clan McGillicuddy and The McGillicuddy Serious Party.
Inspired in part by the antics of Wendyhouse, the Big Muffin Serious Band and The Residents, Avant Garbage attempted to integrate performance into the music. Costumes, dance, props, toys and various other instruments were used in and around their songs. They played quirky original compositions with some rock overtones. Gigs included at Waikato University's Wailing Bongo and the basement of the notorious 56 Memorial Drive. An album length cassette, 'De Compost Collection' was recorded by Greg Locke of Orange Recordings. The review in Real Groove magazine was reasonably complimentary. It was released with a gig in late 1995 at Ferrybank Lounge, supported by Nick Thomas and the Botswana Defence Force.