Estudió música en el Kentucky State College y la Wayne State University, antes de empezar a tocar en Detroit, al comienzo de su carrera musical. En Wayne, conoció a Yusef Lateef.

Sus primeros trabajos profesionales fueron con Sonny Stitt, Donald Byrd y Pepper Adams, a finales de los años 1950. En 1962 realiza una gira mundial con el Rolling Along Show donde tocaba, en ocasiones, el contrabajo. Después se instala en Nueva York, donde dirige un quinteto con Kenny Dorham. Más tarde trabaja con Horace Silver (1964-1965), Freddie Hubbard y Herbie Hancock. En 1972 formó parte, durante cuatro meses, de la banda de jazz-rock Blood, Sweat & Tears, en sustitución de Fred Lipsius. Tras dejar la banda, se dedica a dirigir sus propias formaciones, en colaboración con el bajista Ron McClure.

A mediados de los años 1980, se dedica a la enseñanza, en San José, California, además de dirigir diversos cursos en Europa. Paralelamente, toca como músico de sesión en numerosas grabaciones y conciertos. En 1987 trabajará con Charlie Haden y Al Foster. Después, en los 90, dirigirá su propio grupo.

Henderson comenzó con un sonido en el tenor claramente deudor de John Coltrane, por su calidez y fraseo, aunque nunca dejó de explorar y enriquecer su estilo, lírico y de técnica intachable. Era también un improvisador audaz que, sin embargo, nunca pareció atrevido debido a que su sonido no tenía la agresividad del free jazz de la época.^[1]​

Blue Note Records

• 1963: Page One
• 1963: Our Thing
• 1964: In 'n Out
• 1964: Inner Urge
• 1966: Mode for Joe
• 1985: The State of the Tenor: Live at the Village Vanguard, Vols 1 & 2

Milestone Records

• 1967: The Kicker
• 1968: Tetragon
• 1969: Power to the People
• 1970: If You're Not Part of the Solution, You're Part of the Problem
• 1970: Joe Henderson Quintet at the Lighthouse
• 1971: In Pursuit of Blackness
• 1971: Joe Henderson in Japan
• 1972: Black Is the Color
• 1973: Multiple
• 1974: The Elements
• 1975: Canyon Lady
• 1976: Black Miracle
• 1976: Black Narcissus

Verve Records

• 1968: Four
• 1968: Straight, No Chaser
• 1992: Lush Life: The Music of Billy Strayhorn
• 1992: So Near, So Far (Musings for Miles)
• 1994: Double Rainbow: The Music of Antonio Carlos Jobim
• 1996: Big Band
• 1997: Porgy & Bess

Red Records

• 1987: Evening with Joe Henderson - con Charlie Haden, Al Foster
• 1991: The Standard Joe - with Rufus Reid, Al Foster
• 2009: More from an Evening with Joe Henderson

Jazz Door

• 1973: 6tet/4tet - with Kenny Barron, Cedar Walton
• 1994: Live - with Bheki Mseleku, George Mraz, Al Foster
• 2001: Sunrise in Tokyo: Live in 1971 - con Terumasa Hino, Masabumi Kikuchi

Otros sellos

• 1977: Barcelona (Enja) - con Wayne Darling, Ed Soph
• 1979: Relaxin' at Camarillo (Contemporary)
• 1980: Mirror Mirror (MPS)
• 1999: Warm Valley (West Wind) - con Tony Martucci, Tommy Cecil, Louis Scherr

El año indica la fecha de grabación.

• 1963: Kenny Dorham - Una Mas (Blue Note)
• 1963: Grant Green - Am I Blue (Blue Note)
• 1963: Antonio Díaz "Chocolaté" Mena - Eso Es Latin Jazz...Man!
• 1963: Johnny Coles - Little Johnny C (Blue Note)
• 1963: Blue Mitchell - Step Lightly (Blue Note, released 1980)
• 1963: Grant Green- Idle Moments (Blue Note)
• 1963: Andrew Hill - Black Fire (Blue Note)
• 1963: Lee Morgan - The Sidewinder (Blue Note)
• 1963: Bobby Hutcherson - The Kicker (Blue Note, released 1999)
• 1964: Freddie Roach - Brown Sugar (Blue Note)
• 1964: Andrew Hill - Point of Departure (Blue Note)
• 1964: Grant Green- Solid (Blue Note, released 1979)
• 1964: Kenny Dorham - Trompeta Toccata (Blue Note)
• 1964: Horace Silver - Song for My Father (Blue Note)
• 1964: Duke Pearson - Wahoo! (Blue Note)
• 1965: Freddie Hubbard - Blue Spirits (Blue Note)
• 1965: Andrew Hill - Pax (Blue Note, released in part 1975, as a whole 2006)
• 1965: Pete La Roca - Basra (Blue Note)
• 1965: Horace Silver - The Cape Verdean Blues (Blue Note)
• 1965: Larry Young - Unity (Blue Note)
• 1965: Woody Shaw - In the Beginning (Muse, 1983, reeditado en 1989 como Cassandranite)
• 1966: Nat Adderley - Sayin' Somethin' (Atlantic)
• 1966: Joe Zawinul - Money in the Pocket (Atlantic)
• 1966: Bobby Hutcherson - Stick-Up! (Blue Note)
• 1966: Nat Adderley - Live at Memory Lane (Atlantic)
• 1966: Herbie Hancock - Blow-Up (soundtrack) (MGM)
• 1966: Duke Pearson - Sweet Honey Bee (Blue Note)
• 1966: Roy Ayers - Virgo Vibes (Atlantic)
• 1967: McCoy Tyner - The Real McCoy (Blue Note)
• 1968: Nat Adderley - The Scavenger (Milestone)
• 1969: Herbie Hancock - The Prisoner (Blue Note)
• 1969: George Benson - Tell It Like It Is (A&M/CTI)
• 1969: Miroslav Vitouš - Mountain in the Clouds (Atlantic, reeditado 1972)
• 1969: Herbie Hancock - Fat Albert Rotunda (Warner)
• 1970: Mose Allison - Hello There, Universe (Atlantic)
• 1970: Alice Coltrane - Ptah, the El Daoud (Impulse!)
• 1970: Freddie Hubbard - Red Clay (CTI)
• 1970: Freddie Hubbard - Straight Life (CTI)
• 1971: Blue Mitchell - Vital Blue (Mainstream)
• 1971: Luis Gasca - For Those Who Chant (Blue Thumb)
• 1971: Bill Cosby - Bill Cosby Presents Badfoot Brown and the Bunions Bradford Funeral Marching Band (Uni)
• 1972: Bill Evans / George Russell Orchestra - Living Time (Columbia)
• 1973: David Amram - Subway Night (RCA Victor)
• 1973: Babatunde Olatunji - Soul Makossa (Paramount)
• 1973: Ron Carter - All Blues (CTI)
• 1973: Johnny Hammond - Higher Ground (Kudu)
• 1973: Flora Purim - Butterfly Dreams (Milestone)
• 1973: Charles Earland - Leaving This Planet (Prestige)
• 1974: Luis Gasca - Born to Love You (Fantasy)
• 1974: Patrice Rushen - Prelusion (Prestige)
• 1975: Kenny Burrell - Ellington Is Forever, Ellington Is Forever Volume Two (Fantasy)
• 1976: Coke Escovedo - Comin' at Ya! (Mercury)
• 1976: Roy Ayers - Daddy Bug & Friends (Atlantic)
• 1976: Rick Laird - Soft Focus (Timeless Muse)
• 1977: Flora Purim - Encounter (Milestone)
• 1977: Richard Davis - Way Out West, Fancy Free
• 1977: Woody Shaw - Rosewood (Columbia)
• 1978: Freddie Hubbard - Super Blue (Columbia)
• 1979: Roy Haynes - Vistalite (Galaxy)
• 1979: Jerry Rusch - Rush Hour (Jeru/Inner City)
• 1979: Ron Carter - Parade (Milestone)
• 1979: Art Farmer - Yama (CTI)
• 1979: J. J. Johnson - Pinnacles (Milestone)
• 1980: George Gruntz Concert Jazz Band - Live at the "Quartier Latin" Berlin (MPS)
• 1980: Joanne Brackeen - Ancient Dynasty (Tappan Zee)
• 1980: James Leary - Legacy (Blue Collar)
• 1980: (All-Star Band) - Aurex Jazz Festival: Jazz of the 80's (Eastworld)
• 1981: Chick Corea - Live in Montreux (Stretch, released 1994)
• 1981: Freddie Hubbard - A Little Night Music (Fantasy, released 1983)
• 1981: Lenny White - Echoes of an Era (Elektra Musician)
• 1981: Stanley Clarke, Chick Corea, Joe Henderson, Freddie Hubbard, Lenny White - The Griffith Park Collection (Elektra Musician)
• 1982: Mal Waldron - One Entrance, Many Exits (Palo Alto)
• 1982: Lenny White - The Griffith Park Collection 2: In Concert (Elektra Musician)
• 1982: Lenny White - Echoes of an Era 2: The Concert (Elektra Musician)
• 1983: Dave Friesen - Amber Skies (Palo Alto)
• 1986: Randy Brecker - In the Idiom (Denon)
• 1986: The Paris Reunion Band - For Klook (Gazell)
• 1987: Wynton Marsalis - Thick in the South: Soul Gestures in Southern Blue, Vol. 1 (Columbia)
• 1987: Neil Swainson - 49th Parallel (Concord)
• 1987: Akio Sasajima - Akio with Joe Henderson (Muse)
• 1987: George Gruntz Concert Band '87 - Happening Now! (HatART)
• 1987: The Paris Reunion Band - Hot Licks (Sonet)
• 1988: Frank Morgan - Reflections (Contemporary)
• 1988: Arnett Cobb, Jimmy Heath, Joe Henderson - Tenor Tribute (Soul Note)
• 1988: The Paris Reunion Band - Jazzbühne Berlin '88 (Amiga)
• 1988: Mulgrew Miller - The Countdown (Landmark)
• 1988: Akio Sasajima - Humpty Dumpty (BRC Jam)
• 1988: Jon Ballantyne - Sky Dance (Justin Time)
• 1989: Charlie Haden / Joe Henderson / Al Foster - The Montreal Tapes: Tribute to Joe Henderson (Verve)
• 1989: Donald Byrd - Getting Down to Business (Landmark)
• 1990: Renee Rosnes - For the Moment (Blue Note)
• 1990: Ernie Wilkins - Kaleido Duke (Birdology)
• 1990: Kevin Hays - El matador (Evidence)
• 1990: Bruce Hornsby - A Night on the Town (BMG, Henderson on two tracks)
• 1991: Donald Byrd - A City Called Heaven (Landmark)
• 1991: Rebecca Coupe Franks - Suite of Armor (Justice)
• 1991: McCoy Tyner - New York Reunion (Chesky)
• 1991: Donald Brown - Cause and Effect (Muse)
• 1991: Valery Ponomarev - Profile (Reservoir)
• 1991: Walter Norris - Sunburst (Concord)
• 1991: Todd Coolman - Lexicon (Double-Time)
• 1991: James Williams - James Williams Meets the Saxophone Masters (DIW/Columbia)
• 1991: Joe Gilman - Treasure Chest (Timeless)
• 1991: Rickie Lee Jones - Pop Pop (Geffen, Henderson on two tracks)
• 1992: Kenny Garrett - Black Hope (Warner Bros.)
• 1992: Bruce Forman - Forman on the Job (Kamei Records7004CD), Henderson on four tracks
• 1992: Mulgrew Miller - Hand in Hand (Novus)
• 1993: Bheki Mseleku - Timelessness (Verve, Henderson en un tema)
• 1994: Kitty Margolis - Evolution
• 1994: Roy Hargrove - With the Tenors of Our Time (Verve, Henderson en dos temas)
• 1995: Shirley Horn - The Main Ingredient (Verve, Henderson en dos temas)
• 1998: Terence Blanchard - Jazz in Film (Sony)

• Joachim E. Berendt: El Jazz: Origen y desarrollo (Fondo de Cultura Económica. Madrid, 1986. ISBN 84-375-0260-8)

• CARLES, Phillipe; CLERGEAT, André y COMOLLI, Jean-Louis: Dictionaire du jazz. Robert Laffont Edt., París, 1988. ISBN 2-221-04516-5

•   Wikimedia Commons alberga una categoría multimedia sobre Joe Henderson.

• Joe Henderson en Dijazz Radio Archivado el 22 de julio de 2015 en Wayback Machine.

• Discografía