Tolbert grew up in Lincolntown, North Carolina, and studied at Johnson C. Smith University. He played in Dave Taylor's Dixie Serenaders from 1929, recording with them in 1931. In 1934 he moved to New York City, where he played with Charlie Alexander before joining the house band at the Savoy Ballroom. In 1936 he played with Fats Waller, then joined a band fronted by Olympic athlete Jesse Owens in 1937. Shortly afterwards he joined Snub Mosley's band and took control of it after Mosley's departure. Freddie Green, Kenny Clarke, Red Richards, Otis Hicks, Carl Smith and Lem Johnson all played in the band, which recorded in 1939 under the name Tolbert's Gentlemen of Swing. Tolbert recorded with this ensemble for three years for Decca Records. In 1944 the ensemble recorded four sound films of the tunes "No No Baby", "'Tis You Babe", "Blitzkrieg Bombardier", and "Corn Pone".
Tolbert completed studies at Columbia University in 1946 and broke up the group to take a job in Charlotte, North Carolina as a high school music teacher. He became a faculty member at Southern University in Houston in 1948. Later in his life he worked for the American Federation of Musicians and ran a music store.