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, in the last few months of Bush's first term as president. Nearly all songs start with the letter "W" in their title, except for "No W" and the hidden track "Psalm 23". 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. Compared to its subsequent follow-ups, the musical style of the album is more thrash metal-oriented.
Jourgensen describes Houses of the Molé as a "rebirth" album as he started Ministry anew without long time collaborator Paul Barker who left after the Animositisomina tour due to a falling-out. In his autobiography, Jourgensen describes that he wrote "Walrus" as a way to "celebrate" Barker's departure. In it, it has the words "Paul is no longer with us" played backwards on repeat.
Jourgensen has stated that the name Houses of the Molé is a tribute to Led Zeppelin's 1973 album Houses of the Holy. Mole itself is a Mexican sauce made from chocolate that is nearly black in color, an image that Jourgensen believes represents crude oil.
Former drummer Rey Washam criticized Houses of the Molé, claiming to have worked on the album which he received no credit for. He called Jourgensen a "liar" and "full of shit," which prompted him to sever ties with him. In addition, he said "Houses of the Molé" was "the worst [album] title in the world."
This was the first Ministry studio album to not chart on the Billboard 200. Due to slow sales, the band left Sanctuary.