By age 18, Henderson was active on the Detroit jazz scene of the mid-1950s, playing in jam sessions with visiting New York City stars. While attending classes of flute and bass at Wayne State University, he further developed his saxophone and compositional skills under the guidance of renowned teacher Larry Teal at the Teal School of Music. In late 1959, he formed his first group. 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. Henderson's college classmates included Yusef Lateef, Barry Harris and Donald Byrd. He also studied music at Kentucky State College.