Walking on a Dream received 11 nominations at the ARIA Music Awards of 2009, winning seven, including Album of the Year. A special edition of the album, containing a bonus disc of remixes, B-sides, and unreleased tracks, was released on 20 November 2009.
The album was recorded and mixed by Peter Mayes at Soundworks Music Studio in Sydney at various times throughout 2007, with additional recording by Chris Vallejo at Linear Recording, also in Sydney. According to EMI Music Australia's website, the painting of Steele and Littlemore that comprises the album artwork was based on the iconic film posters for Indiana Jones and Star Wars.
Walking on a Dream received generally positive reviews from music critics. At Metacritic, which assigns a normalised rating out of 100 to reviews from mainstream publications, the album received an average score of 61, based on 19 reviews. Andrew Leahey of AllMusic wrote that Empire of the Sun "[festoon] their music with oddball flourishes, androgynous lyrics, and a general sense of theatricality that borders on schizophrenia", concluding, "Like the music it promotes, the cover art is purposely ludicrous, but listeners who have a palette for such whimsy should walk away happy." Martin Robinson of the NME described the duo as "silly but their songs demand to be taken seriously, just like Prince, Ultravox and Bowie."Blender's Tyler Gray stated, "Acoustic guitar strummed in time with dance beats, tinny vocals and tons of slap-back reverb—it's like some magical pop formula concocted long ago by aboriginal Australian shamen [sic] and parceled out ever since to INXS, Midnight Oil, Outback Steakhouse jingle makers and now this turquoise-loving duo." Andy Gill of The Independent opined that the songs "Walking on a Dream" and "We Are the People" "rather resemble The Beloved or Air, sharing with those duos the impression that the music just seems to have settled, like snow, around the melody."
Mike Orme of Pitchfork wrote that "at their indulgent best [the duo] strike a trenchant middle ground between fantasy and historical revisionism", but expressed that "although Empire tries mightily, they collapse underneath too many ideas before the record is even half over." Michael Cragg of musicOMH felt that the album "offers little in the way of musical experimentation" and that "[m]ost of it sounds like a strange amalgam of Fleetwood Mac and MGMT, as if the latter had been transposed from the slightly grubby streets of Brooklyn to the beaches of Australia." Christian Hoard of Rolling Stone noted that the duo "have lots of straightforward pop chops, but they prefer to get wonky with cheesetastic, Eighties-flavored keyboards and nonsense rhymes like 'Hotdog belt donut melt/Magpie knelt by itself'", adding that the album "sounds like Europop on Special K". At The Guardian, Dorian Lynskey commented that "the slick, pastel-wardrobed MOR of the title track and 'We Are the People' demonstrate melodic agility and sun-dazzled charm", but viewed the album as "a ripe cheese, best not consumed whole." Alex Denney of The Observer remarked that "the record settles upon a cooler hue, favouring minor-key shuffles that, at their best, sound like prime Bangles cuts, but tend towards pedestrian 1980s pop hackery at their worst." Tyler Fisher of PopMatters concluded that, "despite the well-developed '80s image, the music emulated is not anything worth reviving."
The ARIA Music Awards of 2009 nominations were announced on 8 October 2009. Empire of the Sun received more nominations than any other artist, with a total of 11. The winners were announced on 26 November 2009.