Bad Religion's follow-up to 2004's The Empire Strikes First was originally rumored to be a double album to be released in 2006, but this was denied by bassist Jay Bentley.

Bad Religion first mentioned the follow-up to The Empire Strikes First in 2005, stating that the band would begin recording it later that year, making it likely that it would be released sometime in 2006.

[4] On January 20, 2006, it was announced that Bad Religion was "almost 100% ready to go back to the studio or to the house" to begin working on the album.

[10] Bentley also told Kristoffer Averheim, the webmaster of the Bad Religion fansite, that the album had been pushed back to late 2006/early 2007.

In January 2007, it was announced that the album would be called New Maps of Hell and the band would work with producer Joe Barresi.

[14] On April 1, Bentley posted an update on the MySpace bulletin board, stating that the band was finally finished recording the album and would soon begin mixing it.

We're getting ready to play the Santa Monica show and head down to Chile, Argentina, Brazil and Mexico for our tour... looking forward to getting back on the road...On March 16, 2007, New Maps of Hell was announced for release and the track listing was revealed.

[16] Discussing the album's title, guitarist Brett Gurewitz stated "We all liked the concept of maps, because we are exploring new material on this record, both musically and topically.

[31] In February and March, the band went on a West Coast tour of the US, consisting of two-night residencies in multiple Californian and Nevadan cities.

[36] The DVD features an hour of a live performance, music videos for "New Dark Ages" and "Honest Goodbye", a showing of Bad Religion making New Maps of Hell and Graffin and Gurewitz recording the seven acoustic bonus tracks.

Three of the tracks are new – "Won't Somebody", "Adam's Atoms" and "Chronophobia" – written specifically for the deluxe edition; the other four are new acoustic versions of older Bad Religion songs.