The song, an anti-war protest, was written during the early stages of the Iraq War in 2003, and was composed on bass guitar by Pallot. The song was issued on downloads only in March 2005, and the following month saw a commercial release on Pallot's album Fires. This original single release peaked at #88 on the UK Airplay Chart in April 2005.
The 2006 reissue of the single was also accompanied by the popular music video which features Pallot and other shoppers engaging in a 'food fight' in a busy supermarket. It received heavy rotation on British music channels with many people praising the humorous setting, however depicting a darker message within. It was directed by Marc Klasfeld.
After the album proved a commercial flop, Pallot toured as a support act for an array of other artists, and in 2006 was signed to 14th Floor Records, impressed by reaction to her live sets. They reissued the album to greater success in the spring, and released Everybody's Gone to War as a commercial single on May 22, 2006, on the back of performances on Top of the Pops and GMTV, as well as a successful radio play hit, the song reaching #3 in the UK airplay chart. In commercial form, the single entered strongly at #37 on download sales alone, and the following week jumped to #14, making it her highest chart peak to date.