The novel Reservation Blues tells the story of several Native Americans who start a band on an Indian Reservation near Spokane Washington. The band encounters many allies and adversaries along the way, but sometimes it is difficult to tell who genuinely wants to help the band and who wants to take something from them.

The story begins when Robert Johnson arrives at the Spokane Indian Reservation. Considered one of the greatest of blues players, Robert Johnson was believed by many to have sold his soul to Satan in exchange for his phenomenal skill at playing guitar. He arrives on the Spokane reservation in search of Big Mom, a woman he believes can help him escape his deal with the devil. Thomas Builds-the-Fire is the first reservation resident to speak to Johnson and when Thomas gives Johnson a ride near Big Mom's house, Johnson intentionally leaves his guitar behind in Thomas's van. After a conversation with the supernatural guitar, Thomas decides to invite two bullies to join him in forming a band.

Victor and Junior have been friends all their life and for as long as they can remember, they have enjoyed picking on Thomas. Nevertheless, Thomas asks Victor to become the lead guitarist and Junior to become the drummer. Thomas will play bass guitar and perform vocals. Because of scant prospects for employment on the reservation, Victor and Junior agree. Thomas gives Victor Robert Johnson's guitar and soon Victor is a guitar master like no one has ever heard before.

The trio practices on the Spokane Indian Reservation and they begin to attract a following. Soon they receive invitations to play at bars outside the Spokane Reservation and at one performance on the Flathead Indian Reservation, they meet two Native American sisters who join the band. Soon the band named Coyote Springs begins to attract a great deal of attention, but some of the characters they meet do not necessarily have the band's best interests in mind. Two white women who own a bookstore in Seattle and have stereotypical views of Native Americans follow the band and attract the interest of Victor and Junior. These two women happen to have the same names as some famous comic book characters. The recording executives that the band encounters seem to be three of the same generals who led nineteenth century military campaigns against Native Americans, and their company is named Cavalry Records.

Reservation Blues is more than merely a comical story of several young Native Americans who want to start a band. It is also the story of how modern day Native Americans continue to face hardships and the peculiar sense of humor that comes from enduring a tough life. Whether it is facing the high rates of alcoholism on the reservation, the stereotypes and prejudice of non-Native Americans, or trying to survive on substandard government-supplied food, the characters of the novel retain a dark and fatalistic sense of humor.