Henderson was born in Cuthbert, Georgia. His father was a principal and his mother taught piano. He attend Atlanta University in Atlanta, Georgia and graduated in 1920. After graduation, he moved to New York City to attend Columbia University for a master's degree in chemistry.
He worked for the Pace-Handy music company as a song demonstrator. He also worked at Black Swan Records as music director and pianist. He also lead the band accompanying singer Ethel Waters. His success in music made him forget about a career in chemistry.
In 1922 he formed his own band, which was resident first at the Club Alabam then at the Roseland, and quickly became known as the best "Colored" band in New York. For a time his ideas of arrangement were heavily influenced by those of Paul Whiteman, but when Louis Armstrong joined his orchestra in 1924 Henderson realized there could be a much richer potential for jazz band orchestration.
Although the band was very popular, Henderson had little success managing the band. He was well regarded as an arranger and his arrangements became influential. In addition to his own band he arranged for several other bands, including those of Teddy Hill, Isham Jones, and most famously, Benny Goodman.
In 1934, Goodman's Orchestra was selected as a house band for the "Let's Dance" radio program. Since he needed new charts every week for the show, his friend John Hammond suggested that he purchase some Jazz charts from Henderson. Many of Goodman's hits from the swing music were arranged by Henderson for his own band in the late 20s and early 30s.
In 1939 he disbanded his own band and joined Goodman's, first as both pianist and arranger and then working full time as arranger. He reformed bands of his own several times in the 1940s, toured with Ethel Waters again in 1948 - 1949. Henderson suffered a stroke in 1950 resulting in partial paralysis that ended his days as a pianist. He died in New York City.
A good source for information on Fletcher Henderson is The Fletcher Henderson Story a 3 CD Box Set sampling Henerson's music with extensive liner notes by jazz scholar Frank Diggs.