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 Ussleton, 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 album Twilight Time was a tribute to the mix of musical styles he encountered in the local club scene of Chattanooga, such as the AmVets 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). He has provided original music for Ron Shelton's films Blaze and White Men Can't Jump.