He began playing in local clubs with the encouragement of East Ridge, Tennessee High School band director and drummer Chet Hedgecoth and professional reed player Billy Usselton, who appeared as a guest at a stage band festival and heard Wallace with the East Ridge High School Swing Band. After studying clarinet at the University of Tennessee, Wallace settled in New York in 1971 with the encouragement of Monty Alexander, who hired him and recommended him to the American Federation of Musicians local, which virtually guaranteed his entry. Wallace played with Barry Harris, Buddy Rich, Dannie Richmond. His debut recording was done with Flip Phillips and Scott Hamilton in 1977. He has cited Sonny Rollins and Coleman Hawkins among many major saxophone influences. He recorded on the revived Blue Note label in 1985; the original label provided much of the key music of his formative years, and the eclectic cast on the album Twilight Time reflects the mix of musical styles he encountered in the local club scene of Chattanooga, such as the Blue Room, the AmVets Club and Katie's Four O'Clock Club. Country & western, western swing, and rock & roll all required familiarity with key signatures and repertoire favored by "pickers" (guitarists). Wallace toured and recorded with trombonist Ray Anderson (musician), whose technical skills allowed both musicians to explore a broad repertoire not always associated with jazz music. He has provided original music for Ron Shelton's films Blaze and White Men Can't Jump.