Bostic's distinctive style, strong on the sax and heavy on the beat, was quite successful in the rhythm and blues market in the 1950s. One of the few jazz musicians of his generation with formal training, Bostic studied composition at Xavier University in New Orleans in the early 1930s, and then spent several years performing with territory bands in the Midwest as well as with Fate Marable, who led one of the last Mississippi riverboat bands.
His reputation as a superb instrumentalist earned him an invitation to come to New York City, where he played with Hot Lips Page and Lionel Hampton. After a couple of years with Hampton, during which he became more and more active as an arranger, Bostic left to work as a free-lancer, writing for bands such as Jack Teagarden's and Louis Prima, and taking occasional playing jobs. He was a regular at the legendary sessions at Minton's nightclub, where Charlie Christian, Dizzy Gillespie, Thelonious Monk, and others helped create what became known as bebop, and Bostic was considered one of the hottest players on that stage.