Henry James Allen Jr. was born on January 7, 1908 in Algiers, Louisiana — the son of the leader of the Allen Brass Band, one of the great New Orleans parade bands. He took trumpet lessons from Peter Bocage and Manuel Manetta and was playing with the Excelsior Brass Band and riverboat orchestras by the early 1920s. After work with Fate Marable on the Mississippi and a stint with King Oliver in Chicago, he arrived in New York in 1929 to join Luis Russell's Orchestra — and to record for Victor as that label's answer to Okeh's Louis Armstrong.
His early Victor recordings reveal a fully formed genius: a phrasing and rhythmic freedom that anticipated bebop by a decade, a gruff warm tone, and vocals of considerable character. He starred with the bands of Fletcher Henderson and the Mills Blue Rhythm Band, recording his signature hit "Ride, Red, Ride" with the latter.