Joe Williams was born Joseph Goreed on December 12, 1918, in Cordele, Georgia, the son of Willie Goreed and Anne Beatrice Gilbert. When he was about three, his mother and grandmother took him to Chicago, where he grew up on the South Side and attended Austin Otis Sexton Elementary School and Englewood High School. His mother played organ at the family's Methodist church, and he sang spirituals there and picked out tunes at the piano. In the 1930s he sang in a gospel group, the Jubilee Boys, performing in Chicago churches.

He began working as a professional soloist in 1937 and moved through the big-band world of the period: he sang with Jimmie Noone's Apex Club Orchestra from 1937 and toured the Midwest with Les Hite. In 1941 he traveled to Memphis with Coleman Hawkins, in 1943 he sang with the Lionel Hampton orchestra in Boston, and in 1945 he was with Red Saunders at Chicago's Club DeLisa. In 1946 he was in New York with Andy Kirk, with whom he made his first recording. Illness kept him off the road for much of the late 1940s, and he worked as a theater doorman and a door-to-door cosmetics salesman between engagements. By October 1950 he was back at the Club DeLisa with Saunders, and it was there that Count Basie heard him. In July 1952 he recorded "Every Day I Have the Blues" in Chicago with King Kolax's orchestra, issued that September on Checker.

From 1954 to 1961 Williams was the male vocalist with the Count Basie Orchestra. His 1955 recording of "Every Day I Have the Blues" with the band, issued on the album Count Basie Swings, Joe Williams Sings (Clef), reached number two on the R&B chart, and it and "Alright, Okay, You Win" became the best-known songs of the partnership. AllMusic credits him with helping audiences forget the absence of Basie's long-time blues shouter Jimmy Rushing and with reviving the band's fortunes. The 1955 recording of "Every Day I Have the Blues" was added to the Grammy Hall of Fame in 1992. Williams followed it with The Greatest!! Count Basie Plays, Joe Williams Sings Standards (Verve, 1956), which showed his command of the ballad and standard repertoire, and recorded his first album under his own name, Sings Everyday, for Regent in 1956. He sang with the Basie band in two films, Jamboree (1957) and Cinderfella (1960), and appeared with Basie at the 1957 Newport Jazz Festival.

After leaving the band in 1961 he built a career as a soloist at festivals, in clubs and on television, while staying on good terms with Basie and appearing with the orchestra regularly. He recorded and toured with Harry "Sweets" Edison in 1961 and 1962, with Junior Mance from 1962 to 1964, with George Shearing in 1971, and with Cannonball Adderley from 1973 to 1975, and in 1977 he made a long tour from Egypt to India with Clark Terry. His recordings for Roulette, RCA Victor, Solid State and Blue Note in the 1960s and early 1970s included Jump for Joy (1963) and Presenting Joe Williams and Thad Jones/Mel Lewis, the Jazz Orchestra (1966). Between 1970 and 1990 his own small groups usually included the pianist Norman Simmons, and often the guitarist Henry Johnson. In 1985 he toured Europe and the United States with Thad Jones and the Basie orchestra, and later he toured again with the band under Frank Foster.

Nothin' but the Blues (Delos, 1984), made with Red Holloway's Blues All-Stars, won him the Grammy Award for Best Jazz Vocal Performance and was named traditional blues album by the Blues Foundation. He was nominated for seven further Grammys, and in the late 1980s he signed with Verve, for which he made Every Night: Live at Vine St. (1987). Outside music he acted: a supporting part in the 1970 film The Moonshine War, a 1982 appearance as the jazz musician Sonny Goodman in an episode of Lou Grant, repeated guest spots on Sesame Street, and three episodes of The Cosby Show as Al Hanks, father of Clair Huxtable. In later years he worked often in hotels and clubs in Las Vegas, at festivals and on cruise ships, sang with Louie Bellson in Duke Ellington's suite Black, Brown and Beige, and in about 1993 or 1994 toured once more with Shearing.

He received an honorary doctorate of music from Berklee College of Music in 1988 and the same year set up the Joe Williams Every Day Foundation with his wife Jillean to fund scholarships for young musicians. He had lived with respiratory problems for much of his career. After about a week in Sunrise Hospital in Las Vegas, he left on March 29, 1999, and collapsed on a street not far from his home; he passed away that day at 80. The coroner reported natural causes. He was added to the ASCAP Jazz Wall of Fame in 2001.

Williams sang in a smooth, rich baritone, and AllMusic's John Bush called him the last great big-band singer. His repertoire ran across the blues, ballads, popular standards and jazz, and his records pair the Basie band's blues material with orchestral standards albums such as The Greatest!! and A Man Ain't Supposed to Cry (1958). The Basie years put him in front of one of the great swing rhythm sections, and later records placed him in settings from the Thad Jones/Mel Lewis big band to a small group led by Red Holloway and the string-orchestra ballads of Here's to Life (1994). Down Beat readers and the readers of other magazines repeatedly voted him the top male jazz singer. As the Basie band's featured blues singer he followed Jimmy Rushing, and the two are often named together in accounts of the band's vocalists.