Throughout his years with Ellington, and on many occasions under his own name, Cootie consistently displayed a vigorous command of his instrument. Whether playing the muted colourful compositions of Ellington, or playing in the full-throated manner that reflected his admiration for Louis Armstrong, the distinctive trumpet playing of Cootie Williams remains one of the lasting joys of jazz.
He was born, Charles Melvin Williams, in Mobile, Alabama, on 10 July 1911. As a small child, he played various instruments in school bands but then took up the trumpet on which he was largely self-taught. He was barely into his teens when he began playing professionally. Among the bands with which he played in these years, the mid 1920s, was the band run by the family of Lester Young. He continued to play in territory bands, mainly in the south, including that led by Alonzo Ross. It was with this band that he played in New York in early 1928, choosing almost at once to quit the band and move on to higher profile engagements. In that same summer, he recorded with James P. Johnson, then with Chick Webb and Fletcher Henderson, and early the following year he was hired by Ellington to replace Bubber Miley. This, Cootie's first spell in Ellington’s orchestra, was to last for 11 years.
At first, Cootie's role in the band required him to play the so- called ‘jungle effects’ originally created by Miley, but his rich open horn sound and his distinctive plunger muted playing quickly became an important part of the palette with which Ellington worked. By the time of his last year with the band, 1940, he was one of the most distinctive musicians amidst a group of highly individualistic players. Ellington, ever alert to the qualities of his sidemen, showcased Cootie in a composition with which the trumpeter would be forever inextricably linked. "Concerto For Cootie", which was recorded in 1940, remains a jazz standard to this day, usually under the title by which it became better known after a lyric was written for it: "Do Nothin’ Till You Hear From Me."
Cootie's work during this first period was not restricted solely to the Ellington band. He made records with other leaders, among them Lionel Hampton and Teddy Wilson. With the latter, he appeared on sessions accompanying Billie Holiday. He was also leader of one of the small groups drawn from within the Ellington band, the Rug Cutters. When Williams left Ellington in 1940, he was briefly with Benny Goodman, playing in both the full band and the sextet. In 1941, Cootie formed his own big band in which, over the rest of the decade, he included several leading swing era musicians, such as Eddie ‘Lockjaw’ Davis and Eddie ‘Cleanhead’ Vinson, as well as a number of the new young beboppers, notably Bud Powell and Charlie Parker.