Forming in Melbourne, Australia in 1994, Rebecca's Empire brought together a group of talented musicians, all of whom had made an impression on the Australian music industry, mostly as session musicians. The group was based around lead singer and guitarist Rebecca Barnard, who had previously worked with Stephen Cummings, the Black Sorrows, and Chris Wilson. Other members were Shane O'Mara (guitar) whose credits included working with Stephen Cummings and Deborah Conway, Michael DenElzen (bass), formerly of Schnell Fenster and Tim Finn's band, and Peter Luscombe (drums), one-time member of the Black Sorrows. Their debut single, "Atomic Electric," was released in 1994, and quickly became a radio favorite. It was a mixture of sublime guitar pop topped by Barnard's girly vocals, a combination not dissimilar to that used by Belly. In 1995, the Take a Look at Happiness EP was released. The lead single from the EP was "Empty," although this disc also featured an unusual take on Pearl Jam's "Alive" and a cover of Led Zeppelin's "Tangerine."
1996 was Rebecca's Empire's breakthrough year. Their debut album, The Way of All Things, was released to critical praise, and became a minor Australian success. Strong singles were released from the album in the form of "In Deep," "So Rude," and the title track. The success of the album was hampered somewhat by only limited touring by the band, courtesy of Barnard becoming pregnant. A two-year hiatus followed for Rebecca's Empire during which time, DenElzen left the group and was replaced by Bill McDonald, another accomplished journeyman musician who had worked with Deborah Conway, Frente, Paul Kelly, and Michael Hutchence's short-lived side project Max Q. 1998 saw the band return with the single "Medicine Man," a taste of their new album Welcome, which was released in 1999. This disc also produced two other singles, "Big Smoke" and "Bad Blood."