Su padre, clarinete, se trasladó con su familia a Nueva York cuando Josph tenía medio año de vida.
Aunque estuvo vinculado al jazz, frecuentó también el mambo (colaborando con los Afro-Cubans de Machito), a través del cual consiguió un gran éxito en 1951 con "This Is Happiness".
Grabó varias sesiones para Prestige en los años cincuenta contando con la colaboración de algunos de los principales músicos del momento, como el batería Max Roach y el piano Billy Taylor.
Sarah Vaughan llegó a grabar su composición original "Serenada".
Holiday es también pintor abstracto, usando como tema a músicos de jazz.