Tempo of the Damned marked their first full-length album of new material since 1992's Force of Habit. This is Exodus' first studio album to feature Jack Gibson on bass. This album is also the result of Steve "Zetro" Souza's return to the band, after Exodus reunited with Bonded by Blood-era lead singer Paul Baloff for the release of their live album Another Lesson in Violence in 1997. Baloff died of a stroke in 2002 and Souza was invited back into the band, although this would prove to be the last album to feature him until 2014's Blood In, Blood Out, for he abandoned the group during their tour in South America in support of the album. Tempo of the Damned was also the last Exodus album to feature longtime guitarist Rick Hunolt. He returned to the band for their European tour in the summer of 2012, but did not officially rejoin. Although this album was also the last to feature drummer Tom Hunting before his second departure, he would later rejoin the band in 2007. Souza would rejoin Exodus as well after his replacement Rob Dukes was fired from the band in 2014.
Tempo of the Damned also marks Exodus' only studio album to contain a song credited to founding member Kirk Hammett, who found greater recognition as a member of Metallica. The others are their 1982 Demo cassette and the 1997 live release, Another Lesson in Violence; the latter featured the song "Impaler". Hammett brought one of "Impaler"'s riffs to the Metallica song "Trapped Under Ice", which was released on their 1984 album Ride the Lightning. Music videos were filmed for the songs "War is my Shepherd" and "Throwing Down," which largely consists of a jam performance.
Tempo of the Damned received a positive review from Allmusic's Eduardo Rivadavia, who awarded the album three stars out of five, saying "all of the much loved Exodus hallmarks are here: lyrics filled with biting, sarcastic social commentary: no-fuss, jagged thrash metal; and unparalleled technical precision." He then finished his review by saying that the album "successfully resurrects Exodus as the potent and formidable thrash machine of old."
Tempo of the Damned sold almost 2,600 copies in its first week of release in the U.S. and over 14,300 copies by September 13th, 2004 in the U.S.