Bàsicament autodidacte, començà aprenent trompeta i després la canvià pel saxòfon. Encara adolescent treballà, entre altres bandes, a la d’Earl Hines. Des del anys vint tocà en orquestres de Harlem i es donà a conèixer a l’orquestra de James Fletcher Henderson, on també aportava arranjaments. Amb J. Hodges, fou el principal exponent de l’època swing del saxòfon contralt, instrument que des del 1933 compaginà amb la trompeta. El 1932 fundà la seva orquestra, que inclogué destacats instrumentistes, com ara, T. Wilson, i després d’un parèntesi a Europa (1935-38), moltes de les primeres figures del bop, com M. Roach, D. Gillespie o J.J. Johnson. El 1935 s’establí a Londres, on durant dos anys treballà per a l’orquestra de ball de la BBC, mentre tocava per Europa amb músics locals, tot realitzant una àmplia tasca de mestratge i divulgació del llavors poc conegut jazz. A partir del 1942 s’instal·là a Los Angeles, on fins el 1946 mantingué una orquestra, tot i que es dedicà principalment a feines d’estudi, component i arranjant per a pel·lícules i per a la televisió. Des del 1946, que abandonà la direcció orquestral, tocà en petits grups.
Durant les dècades dels anys cinquanta i seixanta continuà tocant i enregistrant com a solista mentre escrivia arranjaments per a Sarah Vaughan, Ella Fitzgerald, Ray Charles i Louis Armstrong. Fins els anys noranta continuà tocant com a gran solista (saxo alt i trompeta) als festivals més importants del món. Fou un dels millors improvisadors de jazz i, com a arranjador, un dels principals arquitectes en la creació del llenguatge de big-band. De les seves composicions destaquen When Lights Are Low and Blues In My Heart, i dels nombrosos premis que obtingué, els dos Grammy pels discs Harlem Renaissance (1993) i Elegy in Blue (1995).