While touring in support of 2003's WWIII, band leader Sascha Konietzko discussed the group's plans for the next album: "What we can all agree on, and I'm not saying we disagree on any other things, but everybody was pointing out that it should be really different. There are terms floating around such as, 'More noisy, more dance-y, more electronic and less butt rock." After releasing a single album with Sanctuary Records, the band re-signed with Metropolis Records.
The album had originally been titled FUBAR, in reference to the military acronym standing for "Fucked Up Beyond All Recognition/Repair". However, in June 2005 the band announced they were abandoning that title, and on July 21, 2005, they announced the new title would be Hau Ruck, German for "heave-ho". Hau Ruck is the first KMFDM album without a five-letter word title since 1988's Don't Blow Your Top.