Aunque Ella Fitzgerald era más popular con la gente, la mayoría de los músicos querían grabar con Bilie Holiday. Fue así como en 1938 se juntó con Artie Shaw, quien simplemente la consideraba "la mejor". Durante el periodo en que participó en su grupo tuvo bastantes problemas por ser la única persona negra en grupo de rostros blancos. Finalmente, después de ser insultada muchas veces con el calificativo de "puta negra" y otros improperios, Billie dejó la banda, luego de que la gerencia de un hotel le exigiera entrar y salir por la cocina del establecimiento.

Tras dejar a Artie Shaw, Billie Holiday empezó a cantar en el Café Society, el primer club de jazz con audiencia interracial, fundado por Barney Josephson, un empresario idealista y amante del jazz. La administración, los empleados y los artistas eran personas de color blanco y negro y "Lady Day" fue contratada como la principal atracción. Fue en ese local donde elevó su música a un nivel más glorioso, cantando baladas que hablaban del amor perdido y la traición como "Man I Love","Gloomy Sunday" y "I Cover the Waterfront", entre otros. Así se forjó la imagen de heroína trágica, con que se le asoció toda la vida.

Durante una de las tantas noches cantando en el Café Society, un hombre joven llamado Lewis Allan se acercó al dueño del local con una composición que trataba acerca de los linchamientos de negros que ocurrían en el sur de Estados Unidos. Allan quería que Billie la cantara y ella aceptó. La canción se titulaba "Strange fruit" y su interpretación fue tan conmovedora que el público quedó en completo silencio. Por supuesto que Columbia Records, el sello discográfico de Holiday, no quiso grabar el tema, sin embargo, permitió su edición a través de Comodore, una compañía de jazz más pequeña. Pese a que el tema fue censurado en muchas estaciones de radios, logró una ubicación en las listas de hits radiales de 1939. Su insistencia en cantar una canción de denuncia racial como "Strange Fruit", le acarreó muchos problemas con la policía que no dejó de hostigarla durante toda su vida.