At the close of the decade, Coe met Pantera guitarist Dimebag Darrell in Fort Worth, Texas, and the two musicians, struck by the similarity of the approaches between country and heavy metal, agreed to work together, and began production on the album, with Vinnie Paul and Rex Brown, which was recorded sporadically between 1999 and 2003, and released in 2006, two years after Dimebag Darrell's murder.
Originally the song Rebel Meets Rebel was supposed to be released as a duet with Coe and Phil Anselmo.
Lyrical content ranges from boisterous, cocky songs about getting drunk and stoned to more serious subject matter, such as the anti-racist song "Cherokee Cry", which criticizes the United States government's treatment of Native Americans.
Rebel Meets Rebel features what has been described as a "groundbreaking" mix of country music and heavy metal. Allmusic writer Megan Frye wrote, "On first listen, ["Nothin' to Lose"] sounds awkward—as if someone had spliced a Pantera song together with a David Allan Coe one on their home computer. It doesn't mesh well, and the bass seems too sharp and tinny. But after listening to the album a few times, it starts to make more sense."Dimebag Darrell was praised for his guitar playing, which incorporated elements from thrash metal, as well as dark melodic playing. "Rebel Meets Rebel" features fiddle playing by Joey Floyd.