Wallace was born in Port Townsend, WA in 1939. At 22 months he moved with his mother to California. After spending a little time in the San Joaquin Valley, he ended up settling in Oakland.
His earliest recordings were on the Black Jack Wayne label in 1953. He recorded alongside Screamin Mel Dorsey and Chuck Wayne and the Heartbeats, as well as recording his own original instrumental, Funky. He performed regularly at this time at the Country and Western halls and go go bars of Niles, California. At this time he was playing alongside Rose Maddox, Johnny Cash, and the Black Brothers. As he developed, he became more sought after at all hours jazz joints where he sat in with Dolphy, Chambers, Mingus, Poindexter, Blakey and Smiley Winters. Jimbo's Bop City in San Francisco was the best place around, where every night after 2 a.m. another legend of the jazz would come through the door.