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 are of his own "Hot and Anxious" which later became "In The Mood" and of "Christopher Columbus", which he was one of the writers of but never got the credit (both for his brother). He also wrote another popular song of the big band era called "Big John Special." These were three of the defining songs of the period.
At different times in his career, Horace was pianist and musical director for both Lena Horne and Billie Holiday.