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. Henderson's band also boasted the formidable arranging talents of Don Redman (from 1922 to 1927). (It should be noted that Henderson actually did few arrangements in the 1920s; most of the best 'hot' sides he recorded were arranged by either Don Redman or Benny Carter. As an arranger, Henderson came into his own in the mid-1930s.)
Henderson recorded extensively in the 1920s and early 1930s, recording for nearly every label. He was recording director for the fledgling Black Swan label from 1921-1923. For example, he recorded for Vocalion from 1923-1925 while also recording for Paramount, Columbia, Olympic, Ajax, Pathe, Edison, Emerson, Brunswick, as well as Banner and the other Plaza labels. From 1925-1930, he primarily recorded for Columbia and Brunswick/Vocalion under his own name and a series of acoustic recordings under the name The Dixie Stompers for Columbia's Harmony and associated dime store labels (Diva and Velvet Tone). During the 1930s, he recorded for Columbia, Crown, ARC (Melotone, Perfect, Oriole, etc.), Victor, Vocalion and Decca.
At one time or another, in addition to Armstrong, lead trumpeters included Henry "Red" Allen, Joe Smith, Rex Stewart, Tommy Ladnier, Doc Cheatham and Roy Eldridge on trumpet. Lead saxophonists included Coleman Hawkins, Buster Bailey, Benny Carter and Chu Berry. Sun Ra also worked as an arranger during the 1940s during Henderson's engagement at the Club De Lisa in Chicago. Sun Ra himself said that on first hearing Henderson's orchestra as a teenager he assumed that they must be angels because no human could produce such beautiful music.
Beginning in the early 1930s, Fletcher's piano-playing younger brother, Horace Henderson contributed to the arrangements of the band. He later led a band of his own that also received critical acclaim.
Although the band was very popular, Henderson had little success managing the band. He was well regarded as an arranger - he started arranging around 1931, or so - 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.
While Henderson's music was loved by the masses, his band began to fold with the 1929 stock market crash. The loss of financial stability resulted in the selling of many arrangements from his songbooks to the later-to-be-acclaimed "King of Swing" Benny Goodman.
In 1939 he disbanded his own band and joined Goodman's, first as both pianist and arranger and then working full-time as the staff 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.
Henderson, along with Don Redman, established the formula for Swing music. The two concocted the recipe every swing band played from (i.e. sections 'talking' to one another, 'hot' swing). Swing, its popularity spanning over a decade, was the most fashionable form of Jazz ever in the U.S.
Henderson was also responsible for bringing Louis Armstrong from Chicago to New York, thus flipping the focal point of jazz in the history of the U.S.
A museum is being established in his memory in his birthplace town, Cuthbert, Georgia.