Els seus primers treballs professionals van ser amb Sonny Stitt, Donald Byrd i Pepper Adams, a la fi dels anys 1950.

El 1962 realitza una gira mundial amb el Rolling Along Show on tocava, de vegades, el contrabaix. Després s’instal·la a Nova York, on dirigeix un quintet amb Kenny Dorham.

Més tard treballa amb Horace Silver (1964-1965), Freddie Hubbard i Herbie Hancock. El 1972 va formar part, durant quatre mesos, de la banda de jazz-rock Blood, Sweat & Tears, en substitució de Fred Lipsius. Després de deixar la banda, es dedica a dirigir les seves pròpies formacions, en col·laboració amb el baixista Ron McClure.

A mitjans dels anys 1980, es dedica a l’ensenyament, a San José, Califòrnia, a més de dirigir diversos cursos a Europa. Paral·lelament, toca com a músic de sessió en nombrosos enregistraments i concerts. El 1987 actuarà amb Charlie Haden i Al Foster. Després, als noranta, dirigirà el seu propi grup.

Joe Henderson va començar amb un so en el tenor clarament deutor de John Coltrane, per la seva calidesa i fraseig, encara que mai va deixar d’explorar i enriquir el seu estil, líric i de tècnica irreprotxable. Era també un improvisador audaç que, però, mai va semblar atrevit causa que el seu so no tenia l’agressivitat del free jazz de l’època.

En tot cas el seu so era molt agradable a l’oïda. I quan va morir era, juntament amb Sonny Rollins, el saxofonista més destacat que quedava de tota la gran fornada posterior al neixement del bop. Ens queda encara en Sonny.