Ouvert à crédit en décembre 1938 par un commerçant de chaussures désargenté d'Atlantic City, Barney Josephson, le Café Society est le premier café-concert et de débats politiques où se produisent les artistes afro-américains qui soit fondé sur l'idée d'un public sans ségrégation, alors que les Noirs sont indésirables dans le public de tous les autres clubs et à peine tolérés au Cotton Club[1]. Le décor du club est excécuté par des artistes du quartier de Greenwich Village comme Ad Reinhardt, Adolf Dehn, William Gropper, Sam Berman, Abe Birnbaum et John Groth[1].
Le succès du Cafe Society est immédiat mais, la clientèle étant peu aisée, le club n'atteint pas l'équilibre financier. L'ouverture d'une annexe sur la huppée 58e Rue amènera un public plus aisé au premier club de Greenwich Village. Toutefois, en 1947, l'arrestation de son frère Leon (qui a prêté de l'argent pour ouvrir le café) pour soupçon de sympathies communistes oblige Barney Josephson à fermer ses cafés[1].
Billie Holiday chante pour la soirée d'ouverture et officie pendant neuf mois. C'est sur cette scène qu'en 1939 elle interprète pour la première fois Strange Fruit[2].