Originally thought to be called Braindead, the title of the album was confirmed via their MySpace website on 22 May 2008 to be Melodia and an official track listing was also announced.

The band began recording in Los Angeles in November 2007 with producer Rob Schnapf, who has also worked on their albums Highly Evolved and Winning Days.

The first single "He's a Rocker" was debuted officially at the 2008 MTV Awards in Australia, on 26 April, with airplay beginning on radio soon after.

"Blue Jam" being a rough early version of "Jamola" with "Hey Now" being an exclusive non-album song.

A limited number of signed copies of the album were made available for online pre-order on 23 June in Australia, whilst Melodia was sold on CD exclusively in the United States by Insound, from 22 July.