Po nieudanych, prowadzonych przez jeden weekend, próbach opanowania instrumentu, zamienił trąbkę na saksofon (o stroju C), usłyszawszy opinię – nota bene błędną – że jest łatwy w nauce. Ostatecznie jednak zdecydował się na saksofon altowy. W zasadzie był samoukiem, a na jego wczesną grę największy wpływ wywarł saksofonista Frankie Trumbauer. Mając 15 lat zaczął grywać w jazzowych klubach Harlemu.
W 1925 przez krótki okres uczył się w przeznaczonym wówczas dla czarnych Amerykanów, Wilberforce College w stanie Ohio, i grał w orkiestrze uczelnianej The Wilberforce Collegians. Następnie jeździł z koncertami wraz z big-bandem Horace’a Hendersona (brata Fletchera), składającym się z byłych muzyków The Wilberforce Collegians. Później doraźnie współpracował z Sidneyem Bechetem, Jamesem P. Johnsonem, Earlem Hinesem i Ellingtonem, aby na rok dołączyć do orkiestry Charliego Johnsona. Był to jego to pierwszy stały angaż. Jednocześnie przez cały czas uczył się (głównie samodzielnie) aranżować muzykę.