As leader
- 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
- 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
- 1971: In Pursuit of Blackness
- 1971: Joe Henderson in Japan
- 1972: Black Is the Color
- 1973: Multiple
- 1973: The Elements
- 1975: Canyon Lady
- 1976: Black Miracle
- 1976: Black Narcissus
- 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
- 1987: Evening with Joe Henderson – with Charlie Haden, Al Foster
- 1991: The Standard Joe – with Rufus Reid, Al Foster
- 2009: More from an Evening with Joe Henderson
- 1973: 6tet/4tet – with Kenny Barron, Cedar Walton
- 1994: Live – with Bheki Mseleku, George Mraz, Al Foster
- 2001: Sunrise in Tokyo: Live in 1971– with Terumasa Hino, Masabumi Kikuchi
- Other labels
- 1977: Barcelona (Enja Records) – with Wayne Darling, Ed Soph
- 1979: Relaxin’ at Camarillo (Contemporary Records) with Chick Corea, either Tony Dumas or Richard Davis on bass, Peter Erskine or Tony Williams drums
- 1980: Mirror, Mirror (Pausa Records) with Chick Corea, Ron Carter, Billy Higgins
- 1999: Warm Valley (West Wind Records) – with Tony Martucci, Tommy Cecil, Louis Scherr
As sideman
- 1963: Kenny Dorham – Una Mas (Blue Note)
- 1963: Andrew Hill – Black Fire (Blue Note)
- 1963: Johnny Coles – Little Johnny C (Blue Note)
- 1963: Grant Green – Am I Blue (Blue Note)
- 1963: Grant Green – Idle Moments (Blue Note)
- 1963: Blue Mitchell – Step Lightly (Blue Note)
- 1963: Antonio Diaz “Chocolaté” Mena – Eso Es Latin Jazz…Man!
- 1963: Bobby Hutcherson – The Kicker (Blue Note – released 1999)
- 1964: Grant Green- Solid (Blue Note)
- 1964: Lee Morgan – The Sidewinder (Blue Note)
- 1964: Kenny Dorham – Trompeta Toccata (Blue Note)
- 1964: Horace Silver – Song for My Father (Blue Note)
- 1964: Andrew Hill – Black Fire (Blue Note)
- 1964: Andrew Hill – Point Of Departure (Blue Note)
- 1964: Freddie Roach – Brown Sugar (Blue Note)
- 1964: Duke Pearson – Wahoo! (Blue Note)
- 1965: Andrew Hill – Pax (Blue Note)
- 1965: Pete La Roca – Basra (Blue Note)
- 1965: Larry Young – Unity (Blue Note)
- 1965: Horace Silver – The Cape Verdean Blues (Blue Note)
- 1966: Nat Adderley – Sayin’ Somethin’
- 1966: Duke Pearson – Sweet Honey Bee (Blue Note)
- 1967: McCoy Tyner – The Real McCoy (Blue Note)
- 1969: George Benson – Tell It Like It Is (A&M/CTI)
- 1969: Herbie Hancock – The Prisoner (Blue Note)
- 1969: Herbie Hancock – Fat Albert Rotunda
- 1970: Freddie Hubbard – Red Clay
- 1970: Freddie Hubbard – Straight Life
- 1970: Alice Coltrane – Ptah, the El Daoud
- 1971: Blue Mitchell – Vital Blue
- 1972: Miroslav Vitouš – Mountain In The Clouds
- 1973: Ron Carter – All Blues (CTI)
- 1973: Flora Purim – Butterfly Dreams
- 1974: Johnny Hammond – Higher Ground
- 1974: Charles Earland – Leaving This Planet
- 1974: Patrice Rushen – Prelusion
- 1975: Kenny Burrell – Ellington Is Forever, Ellington Is Forever Volume Two (Fantasy)
- 1976: Coke Escovedo – Comin’ At Ya!
- 1976: Roy Ayers – Daddy Bug & Friends
- 1977: Flora Purim – Encounter
- 1977: Woody Shaw – Rosewood (Columbia)
- 1978: Freddie Hubbard – Super Blue
- 1979: Art Farmer – Yama (CTI)
- 1982: Mal Waldron – One Entrance, Many Exits
- 1989: Jon Ballantyne – Sky Dance (Justin Time)
- 1991: Wynton Marsalis – Thick In The South: Soul Gestures In Southern Blue, Vol. 1
- 1991: McCoy Tyner – New York Reunion
- 1992: Kenny Garrett – Black Hope
- 1994: Kitty Margolis – Evolution
- 1994: Roy Hargrove – With the Tenors of Our Time
- 1995: Shirley Horn – The Main Ingredient
- 1999: Terence Blanchard – Jazz in Film
- 2004: Charlie Haden/Joe Henderson/Al Foster – The Montreal Tapes: Tribute to Joe Henderson (Verve, 1989)