Born in Cuthbert, Georgia, while later attending Wilberforce University he formed a band called the Collegians, which included Benny Carter and Rex Stewart. This band was later known as the Horace Henderson Orchestra and then as the Dixie Stompers. Henderson left the band to work with Sammy Stewart, then in 1928 organized a new band called the Collegians.Don Redman took over this band in 1931; Henderson continued to work as the band's pianist and arranger before leaving to work for his brother.
He arranged for many of the most important jazz musicians of the era, including his brother. Fletcher Henderson's book contained about as many of Horace's arrangements as of Fletcher's. Although Horace worked continually, led bands, arranged, recorded, and composed into the 1980s, and although he is considered by many the more talented and skillful of the Henderson brothers, Fletcher remained more popular and accomplished more in the field.
Among his better known clients for arrangements, in addition to his brother, were Charlie Barnet, the Casa Loma Orchestra, Tommy Dorsey, Benny Goodman, Earl Hines, and Jimmie Lunceford. His best-known arrangements were of his own "Hot and Anxious" (part of which became the main theme of "In The Mood") and "Christopher Columbus", of which he was one of the writers (but never received credit). He also wrote another popular instrumental of the big band era titled "Big John's Special." These were three important compositions of the period.