Paul Gonsalveswas born in 1920. His first major job, was with Count Basie, whom he joined in 1946 after being released from military service.

Gonsalves joined Duke Ellington in 1950 and stayed with him almost continuously for twenty-four years. Gonsalves replaced Ben Webster, and Ellington was initially attracted to his style because of its Webster-like influences.

Over the years, however, Gonsalves style became more harmonically experimental. He flirted with atonality long before John Coltrane or Eric Dolphy. In fact, his combination of cool atonality with hot rhythms made him one of the most original of all tenor sax men.

Gonsalves' virtuoso performance on "Dimenuendo and Crescendo in Blue" at the 1956 Newport Jazz Festival was largely responsible for a revival of interest in the career and work of Duke Ellington.