After the war Billy Eckstine hired Williams, and following this he worked with John Kirby and Billy Kyle. In 1949 he began the first of several stints with Duke Ellington, who bestowed upon him the nickname "Cadillac". In 1951 he left Ellington's employ and moved to Paris, where he led his own bands and recorded for French labels. He returned to Ellington in 1956, and played with him again in 1969 on a tour of Europe. He died in the Netherlands in 1973.