Wallace moved to Nashville in 1987, where he found work as a demo singer. He sang background vocals on Faith Hill's 1993 album Take Me as I Am. In 1994, Wallace signed to Columbia Records. His debut single, "I'm Listening Now", was released in August 1995. Deborah Evans Price of Billboard gave the song a favorable review, writing that "Wallace has a strong voice and displays a rather moving interpretive ability." It peaked at number 65 on the BillboardHot Country Singles & Tracks chart. Columbia released Wallace's album, Bound and Determined, on October 17, 1995. A second single, "Left Hand of God", was issued the following month.