[1] While later attending Wilberforce University he formed a band called the Collegians, which included Benny Carter and Rex Stewart.

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 other clients for arrangements 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",[2] of which he was one of the writers (but never received credit).

At different times in his career, Horace was pianist and musical director for both Lena Horne[1] and Billie Holiday.