In 2001, Cannibal Ox released their first album The Cold Vein on Definitive Jux, which was the label's first full-length studio album. The Cold Vein received positive reviews from critics and put the duo in the underground hip hop spotlight, and has since been described as one of the best rap albums of the 2000s. In 2003, the group was rumored to have disbanded. However, fellow Definitive Jux rapper Murs said "Can Ox is not broken up, it's just a rumor" between tracks on fellow Definitive Jux rapper Aesop Rock's album Bazooka Tooth. November 2005 brought the release of the live album with a statement in the liner notes hinting at a Cannibal Ox LP to be released summer of 2006. Supposedly, RZA, Pete Rock and El-P were set to contribute. However, the alleged album was never released. In March 2007, El-P answered "I really doubt it" when asked if a new Cannibal Ox album was coming out anytime in the near future. That same year, Vast Aire confirmed that he was no longer working with Definitive Jux, that he left The Weathermen, and that plans for a new Cannibal Ox LP were scrapped. He cited creative and financial differences with El-P and Definitive Jux as well as Vordul's alleged clinical depression. In January 2008, Vast Aire plugged a project entitled Mighty Joseph with rapper Karniege and spoke about future projects in the works. When asked about his relationship with Vordul, he confirmed Vordul as a feature on his upcoming solo LP Deuces Wild. Vast Aire was later featured on Vordul's album Megagraphitti. After many requests for him to produce a second Can Ox album, El-P stated on May 28, 2011 via his Facebook page that "there wont ever be a can ox album produced by me again and thats a fact." On May 31, 2011 Vast Aire released a solo record titled Ox 2010: A Street Odyssey. Vordul is featured in the song "Thor's Hammer." Vast Aire revealed, “We never broke up, but the timing is now right for a new Cannibal Ox LP. Iron Galaxy Records is about to take over.” He also confirmed that he and Vordul Mega are in the studio now working on the album. On April 16, 2013, Cannibal Ox's EP "Gotham" went on sale. The 3-track album contains new songs produced by Bill Cosmiq: Gotham, Gasses in Hell, Psalm 82. Their second album, Blade of the Ronin, was released on March 3, 2015 under iHipHop Distribution to favorable reviews. Bill Cosmiq produced the majority of the album.
