Il commença sa carrière de musicien en 1952, en jouant avec Ramsey Lewis, et fit ses premiers enregistrements comme leader après avoir déménagé à New York en 1958[3]. Il fit ensuite un enregistrement avec le pianiste de jazz Horace Silver sur une version vocale de Señor Blues de Silver, qui fut un succès de juke-box au milieu des années 1950 et demeure une des meilleures ventes en single du label de jazz Blue Note[4]. De plus, Henderson joua et fit des enregistrements avec Oscar Peterson (Bill Henderson with the Oscar Peterson Trio), Jimmy Smith, Count Basie, Youssef Lateef, et Eddie Harris. Il fut sous contrat avec le label Vee Jay de 1958 à 1961, qui enregistra son premier album comme leader, Bill Henderson Sings (1958)[4], accompagné du trompettiste Booker Little.
À partir du milieu des années 1970, il fit des apparitions secondaires à la télévision. Ses rôles au cinéma ont suivi la même tendance, des seconds rôles mineurs. Il enregistra également ses propres bandes sonores comme la chanson King Blues pour la comédie Get Crazy (1983). Il fit une apparition comme invité sur l'album de Charlie HadenThe Art of the Song (1999).