He first gained notice as half of the appropriately named Southern rap duo Rehab. The group's 2000 debut, "Southern Discomfort", spawned a Top 20 single, "It Don't Matter," and preceded a year of high-profile touring. Brooks then signed a solo deal with Jermaine Dupri's So So Def label, and his first album, "Straight Outta Rehab", which features the single "Trailer Fabulous", was released in August of 2003.