Pourtant, qui aurait pu prévoir que Joe Henderson allait devenir un « jazzmaster »…né à Lima dans l’Ohio, une bourgade perdue et loin de toute scène musicale active, dans une modeste famille de 15 enfants, c’est grâce à un de ses grands frères, James T. Henderson, fan de jazz, qu’il découvre la musique au travers de sa collection de disques, notamment les disques de Lester « The Prez »Young, le seigneur du sax ténor, et toute la série des Jazz at the Philarmonic (Il déclare par ailleurs au journaliste Mel Martin, que c’était bien pratique de connaître les solos et les thèmes avant même d’avoir commencé le sax, «… par ce qu’on sait d’avance comment ça doit sonner…»). Doué, travailleur, encouragé par sa famille, il étudie d’abord à Lima, la batterie avec un batteur local, John Jarette, le piano avec Richard Patterson et Don Hurless, et le sax avec son premier professeur, Herbert Murphy. Sa culture musicale commence à se diversifier tout autant que sa pratique; une de ses sœurs aime la musique classique et contemporaine…Joe Henderson découvre que lui aussi, et sans savoir le pourquoi du comment, Stravinsky, Bartök et Hindemith entrent avec plaisir dans son vocabulaire de musicien, si ce n’est même dans son jeu, et surtout dans sa façon totalement stakhanoviste de travailler, d’étudier et d’expérimenter. Il passe un an au « Kentucky State College », puis part courant 1956 pour Detroit, à la Wayne University, où il apprend la flûte traversière et la contrebasse tout en suivant les cours d’harmonie et de théorie de Larry Teal à la Teal School of Music. Il se produit dans les clubs de la ville notamment aux cotés de ses camarades étudiants Yusef Lateef, High Lawson et Donald Byrd qui font à l’époque partie des musiciens phares de Detroit, pour finalement monter sa première formation courant 1959.
A New York
L’expérience aidant, lorsque les drapeaux l’appellent en 1960, c’est tout naturellement dans la musique qu’il va servir. D’abord dans l’orchestre U.S Army Band de Fort Benning en Géorgie, et, parce qu’il gagne la première place avec un quartet au concours « Army Talent Show », il joue pour tous les divertissements de l’armée. Il est choisi à Fort Belvoir en Virginie, pour faire partie du Rolling Along Show, qui voyage autour du monde pour divertir les troupes. Les premières tournées, Okinawa, le Japon, la Corée, Panama, l’Italie, l’Espagne, l’Allemagne, l’Angleterre et la France où il aura l’occasion de jouer avec le batteur Kenny Clarke et le pianiste Kenny Drew à Paris; jusqu’en août 1962 où il est dégagé des obligations militaires. Deux mois plus tard c’est l’arrivée à New York. Lors d’une fête chez le saxophoniste en vogue Junior Cook (sideman dans le Horace Silver’s Quintet depuis 1958), il est présenté au trompettiste Kenny Dorham, fer de lance du label Blue Note depuis le milieu des années 1950. A la fin de la soirée, celui-ci propose d’aller voir Dexter Gordon au Birdland, le club mythique de la 52ème rue où le prince du ténor dirige la « jam session » tous les lundi. Joe Henderson fait un carton ce soir la et partage les applaudissements du public au même titre que Dexter Gordon lui-même. A partir de ce moment la, il rejoint le quintette de Kenny Dorham et enregistre avec lui le disque Una Mas , le 1er avril 1963. Herbie Hancock est au piano, Tony Williams (19 ans lors de cette séance) à la batterie et Butch Warren à la contrebasse, c’est la toute première fois que Joe Henderson entre en studio, pour Blue Note qui plus est, la qualité de sa prestation est telle, qu’on lui fait confiance pour jouer ce qu’il veut. Kenny Dorham le recommande alors chaudement au label, pour des enregistrements à son nom en tant qu’artiste principal. Aussitôt dit aussitôt fait, le 3 juin 1963, Joe Henderson retourne aux Van Gelder Studios, cette fois-ci pour y enregistrer son premier opus , Page One, avec Kenny Dorham, Butch Warren, McCoy Tyner au piano et Pete La Roca à la batterie. Cet album, mélange de Bossa Nova et de Hard-bop, va placer le jeune ténor de Lima, en tête des listes des « sidemen » (accompagnateurs) chez Blue Note.