The band recorded their second studio album after they recorded "The Animal Song" for the soundtrack to the film The Other Sister. The majority of the album was written by Hayes in New York in September 1999 or slightly earlier that year. The exception was 'You Can Still Be Free', a much older song that dated back to at least 1995 - a demo recording appeared on their 1995 demo tape, then titled 'Free'. It has not been made clear why the song was rerecorded, but it is largely a similar arrangement to the original demo. Preceded by the second single "I Knew I Loved You", the album was released on 9 November 1999 to worldwide success. The album spawned a further five singles, one of which was exclusive to the Australian market ("Chained to You"), and one of which was exclusive to the British market ("The Best Thing").
Following the success of the Superstars and Cannonballs video album, the album was reissued in November 2000, containing a bonus live album, Declaration, featuring recordings from the concert at the Brisbane Entertainment Centre on 21 May 2000. Including sales of the re-issue, the album has sold more than 8 million copies worldwide, being certified platinum in a number of countries. It became the band's last studio album after Daniel decided to leave in 2001.
Similarly to Savage Garden, the album's track listing varied internationally. The Australian version of the album features a bonus remix of "The Animal Song", a CD-ROM featuring video footage and bonus material, and the uncut version of "Gunning Down Romance". The International version removes the remix, CD-ROM and features a cut version of "Gunning Down Romance", due to a manufacturing error where six seconds of music are cut between 4:36 and 4:42, causing the music to stop abruptly.