The album is the first part of the band's anti-Bush trilogy, followed by Rio Grande Blood (2006) and The Last Sucker (2007). It was released in the run up to the 2004 American presidential elections, with George W. Bush being president at the time of its release. Nearly all songs start with the letter "W" in their title. The first track on the album, "No W", features numerous satirical samples of Bush's speeches, particularly samples in which he spoke of his war on terror.
The musical style of the album is more thrash metal-oriented than Ministry's previous releases.
Al Jourgensen has stated that the name Houses of the Molé is a tribute to the Houses of the Holy album, released by Led Zeppelin in 1973. Mole itself is a Mexican sauce made from chocolate that is nearly black in color, an image that Jourgensen believes represents crude oil.
This was the first and so far only Ministry studio album to not chart on the Billboard 200. Due to slow sales, the band left Sanctuary. Houses of the Molé is noteworthy for being the first Ministry LP not to feature longtime collaborator Paul Barker since Twitch in 1986. It is also the first album to use Ministry's new logo, as well as their first with Mike Scaccia on guitar since 1996's Filth Pig.