Jewel explained her creative process for "Who Will Save Your Soul" in an interview.
"When I was about sixteen years old I took a train from Michigan to San Diego and then into Tijuana and hitchhiked around Mexico. It seemed like everybody else was looking for somebody to save them. I wrote it during that trip, but I had no idea it would ever be on a record."
The original version of "Who Will Save Your Soul" was never released on Pieces Of You: during the process of picking songs, it was decided that it would be re-recorded. The radio version is missing a verse and samples more of a pop/folk sound than the folk acoustic sound the album primarily consists of.
A commercial single of Who Will Save Your Soul was released in the United States in 1996. It became her first hit single, peaking at number 11 on the Billboard Hot 100.