Henderson werd geboren in Cuthbert te Georgia. Zijn vader was een conrector en z'n moeder gaf pianolessen. Hij ging naar de Atlanta University in Atlanta waar hij in 1920 afstudeerde. Hierna verhuisde hij naar New York om op de Columbia University een diploma op het gebied van natuurkunde te halen. Maar omdat zijn kansen op het vinden van een baan op dat gebied gering zouden zijn richtte hij zich op de muziek. Hij ging werken voor Pace-Handy waarvoor hij liedjes demonstreerde. Bovendien werkte hij bij Black Swan Records als pianist en zat hij in de begeleidingsband van zangeres Ethel Waters.
Ondanks het feit dat zijn band enorm populair was, lukte het Henderson niet goed zijn band te leiden. Na een ernstig auto-ongeluk in 1928 leek hij zijn interesse in de zakelijke kant kwijt te raken en werd hij bekend als ongedisciplineerd. Desondanks bleef hij wel een belangrijke schrijver. Zo schreef hij nummers voor de bands van Teddy Hill, Isham Jones en Benny Goodman.
De samenwerking met Benny Goodman ging geruime tijd door. Toen Goodman in 1934 werd gevraagd om de huisband van het radioprogramma Let's Dance te worden kocht hij een groot aantal nummers die Henderson aan het begin van de jaren 30 had geschreven. In 1939 verliet hij zijn eigen band om zich te voegen bij Goodman, in eerste instantie als schrijver en pianist, maar later alleen als schrijver. Hij richtte zijn band meerdere malen opnieuw op in de jaren 40 en hij toerde tussen 1948 en 1949 met Ethel Waters. In 1950 kreeg hij een hartaanval waardoor hij gedeeltelijk verlamd raakte en moest stoppen als pianist. Twee jaar later overleed hij in New York.