When he was four, Luther Henderson moved to Harlem with his family and became neighbors with Duke Ellington. Ellington would become a major influence on Henderson's life, beginning in the late 1940s and early 1950s when he adapted and orchestrated some of Ellington's larger works, such as Harlem A Tone Parallel and Three Black Kings, for performance in a concerto grosso format by Henderson's orchestra and another symphony orchestra. Henderson's classical training at the Juilliard School and music study at New York University led Ellington to dub Henderson his classical arm. His talents included composing, arranging, conducting, and performing, and he was hired by Ellington in 1946 to orchestrate his Broadway musical, Beggar's Holiday.
Henderson worked on more than 50 Broadway productions in various capacities. For Ain't Misbehavin', he was the original pianist as well as orchestrator, arranger, and musical supervisor. For Lena Horne: The Lady and Her Music, he was the musical consultant and arranged several selections. He orchestrated such musicals as the Tony Award-winning Raisin, Play On!, and Jelly's Last Jam. As a dance arranger, Henderson's credits included Flower Drum Song, Do Re Mi, Funny Girl, and No, No Nanette. His skill in bringing a jazz sensibility to musical theater was much in demand. For Jelly's Last Jam, he rearranged Jelly Roll Morton's jazz compositions and musical fragments into a hit musical; Ain't Misbehavin' used the music of jazz great Fats Waller as a base.