MCA firmó con la banda en 1996 después de las moderadas ventas de su álbum debut, "Cheshire Cat", y de la creciente popularidad del trío en Australia.