Lewis grew up in Dallas and played in variety shows as a teen. He attended the New England Conservatory of Music, then played in Will Marion Cook's orchestra. When Cook's band was taken over by Sam Wooding, Lewis traveled with him on his tours of Europe, South America, and North Africa, remaining until Wooding disbanded the orchestra in 1931. Following this Lewis set up his own band, Willie Lewis and His Entertainers, which featured some of Wooding's old players and played to great success in Europe. Among those who played under Lewis were Herman Chittison, Benny Carter, Bill Coleman, Garnet Clark, Bobby Martin, and June Cole. Lewis's Entertainers recorded for French label Disques Swing.
In 1941 Lewis disbanded the Entertainers and returned to New York City. He played sparsely after this; he found some work as an actor, but took up waitering as his fortunes declined.