While in Paris, he met Kenny Drew and Kenny Clarke. Then he was sent to Maryland to conclude his enlistment. In 1962, he was finally discharged and promptly moved to New York. He first met trumpeter Kenny Dorham, an invaluable guidance for him, at saxophonist Junior Cook's place. That very evening, they went to see Dexter Gordon playing at Birdland. Henderson was asked by Gordon himself to play something with his rhythm section; needless to say, he happily accepted. 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 soon joined Horace Silver's band and provided a seminal solo on the jukebox hit "Song for My Father". After leaving Silver's band in 1966, Henderson resumed freelancing and also co-led a big band with Dorham. His arrangements for the band went unrecorded until the release of "Joe Henderson Big Band" (Verve) in 1996. From 1963 to 1968, Henderson appeared on nearly 30 albums for Blue Note, including five released under his name. The recordings ranged from relatively conservative hard-bop sessions ("Page One", 1963) to more explorative sessions ("Inner Urge" and "Mode for Joe", 1966). 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", Herbie Hancock's dark and densely orchestrated "The Prisoner", Lee Morgan's hit album "The Sidewinder" and "out" albums with pianist Andrew Hill ("Black Fire" 1963 and "Point of Departure", 1964) and drummer Pete La Roca ("Basra", 1965). In 1967, there was a brief association with Miles Davis's quintet featuring Hancock, Wayne Shorter, Ron Carter and Tony Williams, although the band was never recorded. Henderson's adaptability and eclecticism would become even more apparent in the years to follow. Signing with Orrin Keepnews's fledgling Milestone label in 1967 marked a new phase in Henderson's career. He co-led the Jazz Communicators with Freddie Hubbard from 1967 to 1968. Henderson was also featured on Hancock's "Fat Albert Rotunda" for Warner Bros. It was during this time that Henderson began to experiment with jazz-funk fusion, studio overdubbing, and other electronic effects. Song and album titles such as "Power to the People", "In Pursuit of Blackness", and "Black Narcissus" reflected his growing political awareness and social consciousness, although the last album was named after the Powell and Pressburger film of 1947.