Zaczyna grać hard bop w grupie The Jazz Messengers Arta Blakeya. Nagrywa z nimi kilka albumów, między innymi Mosaic, Buhaina's Delight i Free For All. W czerwcu 1960 wraz z saksofonistą Tiną Brooksem, pianistą McCoy Tynerem, bassistą Samem Jonesem i perkusistą Cliffordem Jarvisem nagrywa pierwszy album firmowany własnym nazwiskiem – Open Sesame. W grudniu, kiedy Ornette Coleman usłyszał jak gra z Donem Cherry, został zaproszony do uczestnictwa w nagrywaniu albumu Free Jazz: A Collective Improvisation.
W maju 1961 zaproszony przez Johna Coltrana Hubbard nagrywa w studiach Atlantic Records Olé Coltrane. W sierpniu tego samego roku we współpracy z saksofonistą Wayne’em Shorterem komponuje jeden ze swoich słynnych tytułów – Ready for Freddie. Grając z Jazz Messengers wyzwala się z wpływów Clifforda Browna i tworzy swój własny styl. Przegląd jazzowy Downbeat przyznaje mu tytuł „New Star”.
W latach sześćdziesiątych nagrał w sumie 36 albumów, z których większość to dzisiaj klasyka. Zaczyna również grać free jazz.