Louis Armstrong va canviar tots els intèrprets de metalls del voltant, però després de Bird, tots els instruments van haver de canviar: bateria, piano, baix, trombons, trompetes, saxos, tot.
Va començar estudiant trombó i tuba, alhora que practicava de forma autodidàctica amb la trompeta, tocant en diverses bandes locals juvenils, en una de les quals coincidir amb Lester Young. El 1928, es trasllada a Nova York, on s’incorpora a la big band de Chick Webb i, ocasionalment, a la de Fletcher Henderson.
El seu primer enregistrament va ser el 1928, amb el grup del pianista James P. Johnson a Nova York, on havia vingut del sud amb els Alonzo Ross’ Syncopators. Un any més tard entra a l’orquestra de Duke Ellington, per substituir a Bubber Miley, romanent amb Ellington fins a 1940, i convertint-se en una de les seves estrelles. Amb Ellington, Williams es va establir com la primera trompeta i, quan se’n va anar, Duke li va dedicar la peça titulada Concert per a Cootie (quan, vint-i-dos anys després, Williams va tornar, Duke va dedicar la peça Nou Concert per a Cootie.
El 1938, Williams va ser un dels convidats al famós concert de Benny Goodman al Carnegie Hall. El 1940 Williams es va unir a l’orquestra de Benny Goodman, un esdeveniment que va fer soroll al món del jazz.
Toca després amb Benny Goodman i amb el sextet de Charlie Christian. Posteriorment, forma la seva pròpia big band, en què incorpora músics talentosos com Bud Powell o Eddie Vinson. Amb aquesta orquestra, o amb petites formacions, es manté com a banda resident del Savoy Ballroom , una de les sales més importants de Nova York, durant gairebé setze anys.
El 1941 Cootie va fundar la seva pròpia orquestra amb la qual, al llarg dels anys, contractaria Charlie Parker, Eddie Lockjaw Davis, Bud Powell, Eddie Cleanhead Vinson, Leonard Gaskin i altres joves músics destinats a ser famosos. Entre 1942 i 1944, quan el seu pianista era Thelonious Monk, Williams va figurar com a coautor de Round Midnight, la famosa peça que, entre altres coses, es convertiria en el tema de l’orquestra, encara que amb tota probabilitat Williams va ser inclòs entre els autors per raons econòmiques.
Cap a finals de la dècada de 1940 Williams -potser seguint el gust del públic negre- es va acostar cada vegada més al rhythm & blues.
Als anys 1960, torna a l’orquestra de Duke Ellington, romanent amb el seu fill Mercer Ellington a la banda reconstruïda després de la mort del duc. Va participar en un gran nombre de pel·lícules musicals juntament amb Ellington.
Williams va ser un dels mestres de la sordina, amb la qual aconseguia mantenir un so punxant i emotiu. En els seus primers temps a la banda d’Ellington, va succeir Miley en la responsabilitat de mantenir el so jungle que la va fer popular. El seu estil estava molt influït per Louis Armstrong, encara que també per King Oliver, i va ser un excel·lent solista, amb un fraseig molt ben articulat i so cristal·lí sense la sordina.