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.
In 1958 Vince moved to Southern California where he picked up work with Paul Bley and Marvin Rainwater. He headed a now legendary Sunday jam session at The Cascades Club in Belmont Shores, from which came the emergence of Kent Glenn, Mark Proctor, Gene Stone, and Warren Gale.
In 1966 Vince moved back to the Bay Area where he found work with alto legend Norman Williams at the Juke Box on Haight St. in San Francisco. Through 1970 Vince recorded three albums with Little John, a fusion rock band on Epic records.