In a career spanning more than four decades, Henderson played with many of the leading American players of his day and recorded for several prominent labels, including Blue Note, Milestone, and Verve.

A hometown drummer, John Jarette, advised Henderson to listen to musicians like Lester Young, Stan Getz, Dexter Gordon and Charlie Parker.

By age 18, Henderson was active on the Detroit jazz scene of the mid-'50s, playing in jam sessions with visiting New York City stars.

[3] By the time he arrived at Wayne State University, he had transcribed and memorized so many Lester Young solos that his professors believed he had perfect pitch.

Shortly prior to his army induction in 1960, Henderson was commissioned by UNAC to write some arrangements for the suite "Swings and Strings", which was later performed by a ten-member orchestra and the local dance band of Jimmy Wilkins.

[3] Although Henderson's earliest recordings were marked by a strong hard-bop influence, his playing encompassed not only the bebop tradition, but R&B, Latin and avant-garde as well.

He played a prominent role in many landmark albums under other leaders for the label, including most of Horace Silver's Song for My Father,[1] Grant Green's Idle Moments, Herbie Hancock's The Prisoner, Lee Morgan's The Sidewinder,[1] and "out" albums with pianist Andrew Hill (Black Fire, 1963 and Point of Departure, 1964)[1] and drummer Pete La Roca (Basra, 1965).

In 1967, there was a brief association with Miles Davis's quintet featuring Herbie Hancock, Wayne Shorter, Ron Carter and Tony Williams, although the band was never recorded.

Though he occasionally worked with Echoes of an Era, the Griffith Park Band and Chick Corea, Henderson remained primarily a leader throughout the 1980s.

Blue Note attempted to position the artist at the forefront of a resurgent jazz scene in 1986 with the release of the two-volume State of the Tenor recorded at the Village Vanguard in New York City.

Seidel said in a 2016 interview with musicologist Joel Geoffrey Harris that he decided to offer Henderson a record deal after hearing him perform live at Fat Tuesdays in New York.

Verve adopted a 'songbook' approach to recording him, coupling it with a considerable marketing and publicity campaign, which more successfully positioned Henderson at the forefront of the contemporary jazz scene.