Es crià a Chicago, on cantà en un quartet de gòspel. Començà a actuar professionalment el 1937 amb Jimmie Noone. Després cantà en diverses formacions, com ara la de Coleman Hawkins (1941) i Lionel Hampton (1943). Durant el període 1954-61 fou el cantant de l’orquestra de Count Basie, en la qual les seves interpretacions baladístiques i de blues li reportaren gran popularitat, especialment el tema Everyday I have the Blues (1955). Williams seguí després una carrera de solista apareixent en clubs, a la televisió i festivals. Seguí cantant de manera esporàdica amb Basie i també actuà i gravà amb altres músics, com ara Harry Edison (1961-62), George Shearing (1971) i Cannonball Adderley (1973-75), i una formació de cordes. Williams redefiní el paper del cantant de big band. Tenia una veu rica de baix baríton i un estil imaginatiu i apassionat.