Tolliver was born in Jacksonville, Florida, where, as a child, he received his first trumpet as a gift from his grandmother. He attended Howard University in the early 1960s as a pharmacy student, when he decided to pursue music as a career and moved to New York City. He came to prominence in 1964, playing and recording on Jackie McLean’s Blue Note albums. In 1971, Tolliver and Stanley Cowell founded Strata-East Records, one of the pioneer artist-owned jazz record labels. Tolliver himself released many albums and collaborations on Strata. Following a long hiatus, he reemerged in the late 2000s, releasing two albums arranged for big band. With Love was nominated in 2007 for a Grammy award for Best Large Jazz Ensemble.
He would later describe his experience: “There was so much going on with the music. Like with bebop, we had a long period of just salivating on. There were all these different idioms within a genre, the avant-garde and free music, bebop still, and of course the music of John Coltrane and Miles. It was just a hell of a period. And then there was also the political scene going on….”