Il semble que Billie ait d’abord testé sa nouvelle chanson auprès d’un public restreint, lors d’une fête privée à Harlem en 1938. Présent ce soir-là, le représentant de commerce Charles Gilmore se souvient du silence qui suivit la chanson, puis des exhortations enthousiastes encourageant Billie à l’interpréter face à un plus large public, ce qu’elle fera peu de temps après au Café Society.

En 1939, le Café Society est l’un des rares night-clubs à ne pas pratiquer de ségrégation racialeLe producteur de disque George Avakian a écrit : le café était l’un des "bons" clubs où les Noirs avaient le droit d’entrer et où on leur donnait même, dans la mesure du possible, les meilleures tables, tandis que les gens en tenue de soirée étaient placés derrière un pilier, ou quasiment à l’entrée de la cuisine.. C’est donc un lieu tout choisi pour interpréter une chanson aussi protestataire que Strange Fruit, à une époque où les droits civiques n’en sont qu’à leurs balbutiementsOn se situe alors seize ans avant l’épisode emblématique de Rosa Parks, refusant de laisser sa place dans un bus.. Lorsque Billie Holiday chante Strange Fruit pour la première fois, le silence se fait instantanément dans la salle. Estomaqués, les auditeurs n’osent pas même applaudir à la fin de la chanson : Quand je l’eus terminée, je n’entendis rien, pas le moindre applaudissement. Ensuite, une seule personne se mit à applaudir nerveusement. Puis tout à coup tout le monde applaudit, se rappelle Billie. Finalement, Strange Fruit se révèle donc être un véritable succès et la chanson vient dès lors naturellement intégrer le répertoire de Billie Holiday. Après la première représentation, Josephson décide de mettre en scène le titre, qui viendra clore chacun des concerts de la chanteuse au Café Society : tandis que la salle est plongée dans le noir complet, un unique petit projecteur éclaire Billie qui doit quitter la scène dès la fin de la chanson, sans jamais revenir saluerJosephson : Je lui avais demandé de partir, point final. Il fallait que les gens se souviennent de Strange Fruit, il fallait qu’ils en aient les tripes secouées..

Après neuf mois passés au Café Society, Billie Holiday se produit ailleurs à New York et dans le reste des États-Unis, choisissant soigneusement les établissements où elle peut interpréter Strange Fruit sans prendre trop de risques. La chanson est devenue célèbre et il n’est pas rare que le public la demande, même si Billie n’accède pas systématiquement à sa requêteLe disc-jockey Daddy-O Daylie : Je lui ai demandé : "Lady, pourquoi vous ne la chantez jamais quand il y a foule ? Pourquoi vous ne la chantez pas plus souvent ?" Je n’oublierai jamais sa réponse : "Je la chante seulement pour les gens capables de comprendre et d’apprécier. C’est pas une chansonnette sur l’amour et l’herbe tendre. Ça parle de souffrance et de chagrin". Elle regardait les gens et, si elle avait l’impression qu’ils n’étaient pas vraiment dans le coup, elle ne la chantait pas.. Tous les témoignages s’accordent pour dire que chacune de ses interprétations reste un moment inoubliable, fascinant, poignant d’émotion. Meeropol, qui a entendu Billie chanter Strange Fruit au Café Society, raconte : Elle en donnait une interprétation ahurissante, très dramatique, saisissante, qui pouvait bousculer le public, le faire sortir de sa bonne conscience n’importe où. C’était exactement ce que je voulais, c’était pour ça que je l’avais écrite. Le style de Billie Holiday était incomparable et rendait l’amertume et le choc que j’avais espéré mettre là-dedans. Le public l’a formidablement acclamée. Pour Billie, l’interprétation de Strange Fruit est souvent une épreuve sur le plan émotionnel : Chaque fois que je la chante, ça me fiche le cafard, raconte-t-elle dans son autobiographie. Mais je dois continuer à la chanter, non seulement parce que les gens me la demandent, mais parce que vingt ans après la mort de mon père, ce qui l’a tué existe toujours dans le Sud.

Pourtant, la chanson est loin de faire l’unanimité. Considérée comme l’une des premières chansons de protestation, elle dérange et provoque parfois des troubles lors de son interprétation : si les moins exaltés se contentent de quitter sobrement la salle, certains plus turbulents n’hésitent pas à manifester plus violemment leur mécontentement. Selon Billie, c’est ainsi que Strange Fruit permet de distinguer les gens corrects des coincés et des tordus. Malheureusement, cette chanson lui vaudra d’être mal vue des autorités. Après son arrestation pour détention de drogue, elle déclare au magazine Down Beat en 1947 : Je me suis fait aussi beaucoup d’ennemis. Chanter ça [Strange Fruit] ne m’a pas aidée.