Частичный запрет профсоюза музыкантов на запись пластинок в середине 1940-х гг. задержал появление Джо Вильямса в центре джазовой сцены на добрый десяток лет. Они нашли друг друга с Каунтом Бэйси лишь в 1950 г. в том же Чикаго, когда пианист возглавлял септет, отказавшись на пару лет от биг-бэнда по экономическим причинам. Тогда Джо впервые пел с Каунтом, и как только этот лидер вновь собрал оркестр, он пригласил к себе чикагского вокалиста. Это был очень удачный музыкальный союз, который принёс феноменальный коммерческий успех.
Вильямс пришёл в бэнд под Рождество 1954 г. и спустя несколько месяцев записал с ним «Every Day I Have The Blues», тему блюзового пианиста и композитора Мемфиса Слима (настоящее имя Питер Чэтмен) в аранжировке саксофониста оркестра Эрни Уилкинса. Эта запись моментально превратила Джо Вильямса в «звезду» международного класса. Впоследствии у него были и другие хиты с оркестром Бэйси («Аll Right, Okay, You Win», «Going To Chicago», «Roll’em, Pete», «In The Evening», «Cherry Red»), в которых уникальные голосовые качества певца сочетались с высоким музыкальным мастерством и блюзовым чувством.
«Это самый свингующий оркестр в мире, и вся наша группа музыкантов до последнего человека получала огромное удовольствие от этой работы», — говорил Вильямс. Они играли всюду, от подвала джаз-клуба «Бёрдлэнд» до крыши отеля «Уолдорф Астория» — в 1957 г. оркестр оказался первым негритянским биг-бэндом, который появился в этом элегантном и дорогом месте. «Мой сын номер один!» — так Бэйси обычно объявлял Вильямса на всех концертах. Но через несколько лет Джо решил идти своей дорогой и в июне 1961 г. покинул бэнд, имея ангажементы на год вперёд. «Я должен был работать в Бостоне, и Бэйси был настолько великодушен, что сам приехал туда и представил меня в первых двух шоу. Он вёл себя как мой поклонник номер один!»
Далее Джо Вильямс выступал с самыми разными джазменами, на фестивалях джаза в Ньюпорте и Монтеррее, на гастролях в Европе и Японии, а также в студиях записи. Есть великолепные диски, которые он в разное время записывал в течение 1960-1970-х гг. с оркестром Тэда Джонса/Мела Льюиса, квинтетом Джорджа Ширинга, октетом Дэйва Пелла и т. д. В фолк-опере Кэннонболла Эддерли «Big Man» он спел главную партию, а в 1983 г. превзошёл себя, когда на концерте в Карнеги-Холле исполнил a capella знаменитый спиричуэлс Дюка Эллингтона «Come Sunday».
Все эти годы (вплоть до 1989 г.) в анкетах критиков и читателей журнала «Down Beat» Джо Вильямс неизменно занимал первое место среди джазовых вокалистов. С 1975 г. он жил в Лас-Вегасе с четвёртой женой, англичанкой Джиллиэн, которую встретил ещё в 1959 г. От третьего брака у него есть сын Джо и дочь Энн.
