Williams was born in Lewisburg, Tennessee, and grew up in Bowling Green, Kentucky, before moving with his parents to Detroit at the age of 13. He started learning saxophone and played in school bands before forming his own band, Paul Williams and his Kings of Rhythm, with trumpeter Lloyd Henderson, in the mid-1930s, and playing in local clubs. The band split up during World War II, and Williams then joined Clarence Dorsey's band. He toured with the band, then known as the Sensational Six, until 1945 when he left to join another local band, led by King Porter (born James A. Pope, 1916–1983)
Williams became known for his showmanship in Porter's band, and made his first recordings with Porter for the Paradise label in 1947. He attracted the attention of agent and record producer Teddy Reig, and, under Reig's tutelage, formed his own band. Credited as the Paul Williams Sextette, they recorded in Detroit for Savoy Records in September 1947, and "Thirty-Five Thirty" reached #8 on the Billboard R&B chart (then called the "race records" chart) in early 1948. Wiliams followed up its success with three further chart hits released in 1948 – "The Twister" (which according to Joel Whitburn "had a 'rockin' beat" and "laid the foundation for Hank Ballard's 'The Twist'"); "Waxie Maxie"; and "Walkin' Around" – all featuring the honking tenor sax of Wild Bill Moore.