During the Always Outnumbered, Never Outgunned tour, the band debuted two new songs, "Warning" and "Dead Ken Beats"; the former features Keith Flint on vocals and consists of heavy bass lines and guitar riffs, while the latter includes a sample of the Dead Kennedys' song "California Über Alles", and vocals by Maxim. At the Sheffield and Birmingham gigs (16 May and 17 May 2008 respectively), the bands played a new version of "Dead Ken Beats", while debuting "World's on Fire", "Warrior's Dance", which became a single from the forthcoming album, and "Unstoppable". At the Gatecrasher festival on 25 May 2008, the band performed a track which would later appear as a B-side to the album named "Mescaline".
The band played another new track during the Their Law tour. The song, which was printed on a setlist as "Heatwave", is thought to have been renamed "Heatwave Hurricane", due to Liam Howlett listing it among his favourite songs in a recent interview. It has been described as "something like a cross between 'Hotride' (live version) and the 'Firestarter' remix". A short clip can be seen on YouTube, revealing that the song includes a sample of "I'm Five Years Ahead of My Time" by The Third Bardo, a song which is also featured on Howlett's Back to Mine compilation.
Recording began in February 2006, shorty after the release of Their Law: The Singles 1990–2005, and ended in[when?]. Some of the songs recorded for the album, such as the synthesizer-led "Colours" were written before the release of the group's fourth album, and early versions were showcased in live performances. Liam Howlett conceived the album musical direction as a mashup of their previous albums. The new album was set to be released in summer 2007, but when the album's release date was postponed to the "first quarter of next year ," the band had conceived over 25 ideas while completing production on certain tracks and writing lyrics.
Howlett revealed in an April 2008 interview that he had three more months of work left for the new album. He also said that he has a working album title and song titles, but was not ready to publicly announce them until these details were released through The Prodigy's official newsletter on 4 November. This announcement stated that the album would be a return to their "old-school but cutting edge" roots, and would feature collaborations with Dave Grohl of Foo Fighters, Them Crooked Vultures and Nirvana, and James Rushent of Does It Offend You, Yeah?, but would not feature any guest vocals.
Invaders Must Die's title track is the album's opening track, and its lyrics include the name of the group on the line "We are The Prodigy." The song is featured in many film and game trailers such as the film Scott Pilgrim vs. the World and the Duke Nukem Forever game trailer. "Omen" has a similar tempo, and both tracks were co-produced by James Rushent. "Thunder" recreates elements from Trevor Joe's "Ethiopian Peace Song" (also known as "Rasta Peace Song"), while "Colours" is one of the first songs written by the band.
"Take Me to the Hospital"'s music video was The Prodigy's first to be released on the Vidzone application. The promotional film was filmed onto VHS rather than digital recording equipment to obtain an old school 1990s look. The track samples "Salami Fever" by Pepe Deluxé and "Ragamuffin Duo Take Charge" by Asher D & Daddy Freddy, and the name of the song comes from the record label of the same name. The melody of "Warrior's Dance" is similar to "Take Me to the Hospital"'s. The song chorus is a sample of the True Faith song "Take Me Away", which was then sampled and edited by Major Players in "Come with Me", the song where the vocals for this track come from. The song also samples "Final Cut", a song featuring Bridget(te) Grace. A festival of the same name was curated by the group, and will take place at Milton Keynes.
"Run With the Wolves", featuring Dave Grohl on drums, who was contributor to many tracks of the Nine Inch Nails album With Teeth (2005), has a sample of "So Refined", a single performed by Senser. This song was featured in the 2011 film Hall Pass. There was a contest to make a music video for the song, and the winning entry was posted on 15 February 2010. After a "reprise" of "Omen", "World's on Fire" follows. This song samples The Breeders' "I Just Wanna Get Along" and "Vamp" composed by Outlander. "Piranha" samples "Troubled Mind" by The Buff Medways and "Sara Zamana" by Kishore Kumar and Chorus, while "Stand Up", the only instrumental track on the album, samples "One Way Glass" from Manfred Mann Chapter Three. This song, along with "Omen", is featured heavily in the 2010 film Kick-Ass, and both are included on the soundtrack release of the album.
Invaders Must Die was chosen as the lead single from the album of the same name, and was released from the band's website as a free digital download on 26 November 2008. The download was announced in a newsletter sent to fans on 24 November, and first aired on Zane Lowe's Radio 1 show as the 'Hottest Record in the World' of the same day it was released. Although it was not released as a commercial single, the song peaked at No. 49 in the UK Singles Chart, whilst the Chase and Status remix reached No. 53 in the Australian ARIA Singles Chart and No. 7 in the ARIA Dance Chart.
The single that followed, "Warrior's Dance", was released on 11 May 2009. The digital version of the single was released on 17 April 2009 in Australia as an iTunes exclusive, while the "Edit" version with none of the remixes is also available. When released there, however, the song was titled incorrectly and the download was actually a song from the Britpop band Placebo; this issue was fixed shorty after its release. Three downloadable remixes of "Warrior's Dance" were sold via the group's website, while an extra remix was exclusive to iTunes. The song peaked at No. 9 on the UK Singles Chart.
"Take Me to the Hospital", released on 31 August 2009, was the final commercially-released single from the album. It was remixed six times, with the "Wreckage" mix being a collaboration with Josh Homme. The song debuted at No. 38 in the UK Singles Chart and topped the UK Dance Chart.
Invaders Must Die was released as a CD, CD/DVD set, double-vinyl, digital download and a luxury-like 7-inch vinyl box set that includes five 7-inches, CD/DVD, bonus CD, poster, stickers and stencils. To coincide with the release of the album, the band embarked on a nine date UK arena tour, with support from Dizzee Rascal, Noisia, Herve and DJ Kissy Sell Out. The "Warrior's Dance" video aired on Channel 4 on 28 March at 12:00 am.
As with Always Outnumbered, Never Outgunned, initial critical response to Invaders Must Die was mixed. At Metacritic, which assigns a normalised rating out of 100 to reviews from mainstream critics, the album received an average score of 60, based on 20 reviews. One example was Allmusic, who called it "a curious nu-rave record, as though the sound of 1991 (such as their Top Ten hit "Charly") has been filtered through the sound of 1996 (such as their number one, "Firestarter") to emerge as nothing more than a hodgepodge of uptempo dance music with extroverted beats and grimy basslines.
However, it was a commercial success. The album debuted at the top of the UK Albums Chart on 1 March 2009 with 97,254 copies sold, giving them their fourth consecutive number one album in the UK. The album performed well worldwide as well, entering the top five in Poland, Ireland, the Netherlands, Australia, Canada, Belgium and Germany. The album debuted at No. 117 in the US but jumped to No. 58 in its second week. The album received Gold sales status in Australia and Germany, while Switzerland classified it as "2x Gold" with 30,000 copies. As of 7 November 2009 the album has sold over 1,029,000 copies worldwide.
The European edition includes a 11-track audio CD and a DVD with the videos for "Invaders Must Die," "Omen" and live performances of "World's on Fire" and "Warrior's Dance". The DVD has a computer-readable (HD data for Microsoft Windows and Mac OS X) high definition version of the former music video. On 21 October 2009, the album was re-released as "Invaders Must Die Special Edition", which included remixes of the album itself, a different album cover, and a DVD containing music videos and live performances. One of the tracks on the edition was eventually released as a MP3 for download. The song was later released as "Invaders". A "Warrior's Dance Fest" edition of the album will be released in Japan alone.