War Party was released on October 26, 2004, and continues the decidedly heavier focus reintroduced in Violence Has Arrived.

Gwar still has more gratuitous violent imagery in "Womb with a View", "Fistful of Teeth" and "Bonesnapper" and retains some trademark silliness in the Beefcake the Mighty-hollered French punk song "The Bonus Plan".

The enhanced CD portion contains a music video for "Womb with a View", which shows a plethora of concert footage from the band's spring 2004 tour.

According to interviews with Todd Evans (Beefcake the Mighty) and Brockie, War Party was selling very well, and was attracting new Gwar fans, as well as seeing old ones come back.

Although not following a true story per se, unlike many of the band's previous albums, there seems to be an ongoing concept throughout the album about a fictional political party named "The War Party", with policies dedicated specifically to the eradication of the human race by supporting global war and hatred, under the "Krosstika", a symbol crossing the Christian cross and the Nazi swastika ("Two great hates that hate great together").