Su llegada a la popularidad se produjo cuando se convirtió en el cantante de la orquesta de Count Basie en 1954, orquesta en la que permanecería durante varios años.