Born in Greenville, South Carolina, Anderson lost both parents when he was four years old, and was sent to live at the Jenkins Orphanage in Charleston, where he learned to play trumpet. Classmates gave him the nickname "Cat" (which he used all his life) based on his fighting style. He toured and made his first recording with the Carolina Cotton Pickers, a small group based at the orphanage. After leaving the Cotton Pickers, Anderson played with guitarist Hartley Toots, Claude Hopkins' big band, Doc Wheeler's Sunset Orchestra (1938–1942), with whom he also recorded, Lucky Millinder, the Erskine Hawkins Orchestra, Sabby Lewis's Orchestra, and Lionel Hampton, with whom he recorded the classic "Flying Home #2".
Anderson's career took off, however, in 1944, when he joined Duke Ellington's orchestra at the Earle Theater in Philadelphia. He quickly became a central part of Ellington's sound. Anderson was capable of playing in a number of jazz styles, but is best remembered as a high-note trumpeter. He had a big sound in all registers, but could play in the extreme high register (up to triple C) with great power (videos exist showing him playing high-note solos without a microphone, clearly audible over an entire big band with all the members individually miked). Wynton Marsalis has called him "one of the best ever" high note trumpeters. More than just a high-note trumpeter, though, Anderson was also a master of half-valve and plunger-mute playing. He played with Ellington's band from 1944 to 1947, from 1950 to 1959, and from 1961 to 1971, with each break corresponding to a failed attempt to lead his own big band.
After 1971, Anderson settled in the Los Angeles area, where he continued to play studio sessions, to gig with local bands (including Louie Bellson's and Bill Berry's big bands), and occasionally to tour Europe. Although his erratic behavior over the last decade (or more) of his life was well documented, it took many by surprise when he died in 1981 of a brain tumor.