Studio work for the album was put on hold in mid 2007 due to vocalist Chad Gray's and guitarist Greg Tribbett's touring commitments with Hellyeah. At the completion of the Hellyeah tour, Mudvayne reunited and began recording with producerDave Fortman, who also produced their previous full-length release, Lost and Found. Having completed the tracking of the drums and guitars, as well as the recording of the bass and vocals, the band announced that the mastering stages were scheduled for completion by October 1, 2008. During the recording phase, Fortman revealed to MTV the tentative title The New Game, adding that the band planned to release a second full-length record six months after its release.
A video previewing a possible album track was uploaded to Mudvayne's MySpace profile on July 16, 2008. A second video appeared on the profile on August 19 showing Gray tracking vocals. The second video was later made a feature on the band's official website. On September 16, 30-second previews of "Fish Out of Water," "A New Game" and "Do What You Do" were made available for streaming on the profile. The first single, "Do What You Do," first received airplay on September 23. Mudvayne also shot a video for "A New Game" and released a second single to radio, "Scarlet Letters," that was first broadcast on March 9, 2008.[clarification needed]
A bonus song, "Fish Out of Water," was made available for download to customers who pre-ordered The New Game on the iTunes Store, or through Best Buy, and the deluxe digital version of the album also included a digital copy of By the People, for the People. On October 28, 2008, "Have it Your Way" was released exclusively by Revolver magazine through its website.
Fortman said the album should please listeners, but also incorporate a distinct rock and roll sound unheard on previous Mudvayne records. "It's heavy and has great hooks, but it also has some moments that are a little more rock 'n' roll that are really cool. It's not anything drastic, but every now and then you'll catch a little hint of old school rock. Also, the tones are a little more earthy sounding and a little warmer than Lost and Found." Singer Chad Gray has stated the album is "not light years away from what we've done in the past, but it's not the same." The album's sound has been compared to Alice in Chains and Motörhead.
The album has received mixed reviews from critics. James Christopher Monger of Allmusic gave the album a mixed review and wrote "The problem is, Mudvayne's own predilection for predictable loud/soft/loud set pieces, forgettable melodies, and over-reliance on words like "sorrow," "rage," "abused," "disease," "nightmares," and "beatings" keeps things from ever leaving the tarmac."