Coleman was born in Portsmouth, Virginia and raised in a music-loving military family that lived in San Diego, San Francisco, Bremerton, Washington, and the Chicago area. With her father playing piano, two brothers on guitar, and a sister who plays guitar and keyboards, Deborah felt natural with an instrument in her hands, picking up guitar at age 8. She has played at the top music venues such as North Atlantic Blues Festival (2007), Waterfront Blues Festival (2002), the Monterey Jazz Festival (2001), Ann Arbor Blues and Jazz Festival (2000), Sarasota Blues Festival (1999), the San Francisco Blues Festival (1999) and the Fountain Blues Festival (1998).
Coleman's Blind Pig debut, I Can't Lose (1997), was an album of ballads and blues stories, and guitar playing and singing. Her version of Billie Holiday's "Fine and Mellow" got a lot of airplay on college and public radio stations around the U.S. Soul Be It (2002) included the opener "Brick", "My Heart Bleeds Blue", "Don't Lie to Me," and a jump blues track, "I Believe". These were followed by What About Love? (2004) and Stop the Game (2007).