...And the Battle Begun

Rx Bandits served as the backing band of the Bruce Lee Band for a series of shows in March 2005.[5] They went on a US West Coast tour with Steel Train, Before Braille and Facing New York.[6] The band recorded their next album in May 2005.[5]

Like The Resignation, the rhythm section was recorded live for ...And The Battle Begun.[7] Overdubs were done in various studios, one of which was Embree's.

They supported Finch in July and August 2005.[8] In September and October 2005, they toured across California with Mike Park and Dan Potthast.[9] The album was originally slated to be released in late 2005 via Drive-Thru Records, but for reasons known only to the band and the label, they decided to part ways, despite the contract stating that one more album was due to the label. The album was eventually pushed back to May 2006[10] and later to October 2006 due to unspecified issues between the label and band. However, by the summer of 2006, both sides had cleared up any disputes, freeing up the album.

Saxophone player Steve Borth, according to the RX Bandits website, left the band to pursue his own musical career, which includes his band Satori. He officially departed the band mid-tour on June 28, 2006, his final performance being in New York City at the Bowery Ballroom the previous day.

The Sacramento News & Review wrote that the album "challenges your ears in the best way possible, with shifting time signatures, wildly varying moods and general chaotic genius. Countless experimental bands mine similar 'anything goes, so long as its good' territory, but rarely has this boundary-pushing been so refreshing."[11]