Несмотря на отсутствие не только музыкального, но и начального общего образования, Холидей стала выступать в клубах и так называемых спик-изи, то есть ресторанах, где нелегально продавались спиртные напитки.
"Однажды, – пишет Д. Коллиер, – как она рассказывает, им с матерью грозило выселение из квартиры. В надежде найти работу Билли отправилась на 132-ю улицу Гарлема, где находилось несколько небольших клубов. Владельцу одного из них, Джерри Престону, она сказала, что умеет танцевать. Однако танцевала она плохо. Тогда пианист, пожалев ее, спросил, может ли она что-нибудь спеть. Билли исполнила популярные в то время песни «Travlin All Alone» и «Body and Soul». Посетители сидели как завороженные. Триумф был полный, и Билли сразу получила свои первые заработанные деньги.
Трудно сказать, правдива ли эта история. Во всяком случае, с той поры Билли начала работать в клубах на 132-й улице. Там в 1933 году ее и нашел вездесущий «открыватель талантов» Джон Хэммонд. Холидей сделала свои первые записи с только что организованным оркестром Бенни Гудмена, заключила контракт с менеджером Джо Глейзером".
В конце 1933 года Холидей записала с небольшим студийным оркестром Бенни Гудмена несколько песен. И хотя роль певицы сводилась главным образом к тому, чтобы подчеркнуть мастерство Гудмена, ее оригинальная манера пения заставила обратить на себя внимание.
В самом конце 1934 года она выступила вместе с пианистом Бобби Хендерсоном на подмостках театра «Аполло», самого известного развлекательного клуба в Гарлеме. Отзывы того времени о ее исполнении нельзя назвать благожелательными: расслабленная, так называемая ленивая манера пения дисгармонировала с общим направлением театра. Но вскоре, выступая уже с оркестром Ральфа Купера, Холидей добилась популярности и с этого же времени стала называться Билли.
В 1935 году на экраны вышел фильм «Симфония в черном», в котором молодая певица снялась с большим успехом – вместе с Дюком Эллингтоном.
Вскоре Хэммонд решил организовать выступление Билли с малыми ансамблями во главе с Тедди Уилсоном, которые делали записи для музыкальных автоматов. Первая такая запись относится к 1938 году, а затем в течение шести лет Билли записала более сорока пластинок. Она работала практически со всеми ведущими джазменами. Среди них – Бенни Гудмен, Бен Уэбстер, Рой Элдридж, Джонни Ходжес, Гарри Карни, Бенни Мортон.
Лучшие записи, по ее собственному признанию, были произведены в содружестве с Тедди Уилсоном, трубачом Баком Клейтоном и саксофонистом Лестером Янгом. С Янгом, звавшим певицу Леди Дэй, у Билли долгое время сохранялись очень теплые отношения. С ним Холидей удавались, пожалуй, самые виртуозные интерпретации. Взаимодействие ее и Янга в таких песнях, как «Что для меня?» или «Любимый мой», воистину безупречно. Эти и некоторые другие ее записи в период между 1935 и 1942 годами считаются лучшими за всю историю джаза.
К тому времени Билли уже добилась известности и была тут же принята в оркестр Арти Шоу. Музыканты и сам Шоу старались поддержать Билли, однако во время концертов то и дело возникали конфликты на расовой почве. В результате Билли в 1939 году покинула оркестр. На помощь вновь пришел Хэммонд. Он познакомил Билли с Барни Джозефсоном, владельцем кафе «Сесайети», и тот предложил ей работу.
Вряд ли где-нибудь еще Билли Холидей нашла бы такую публику, как в кафе «Сесайети». Для артистки ее склада это идеальное место работы. Сюда приходили не только музыканты и знатоки джаза, но и люди, готовые выразить сочувствие талантливой негритянской певице, испытывающей страдания и унижения из-за цвета кожи. Некоторые завсегдатаи кафе имели связи и влияние, они стали покровительствовать ей. И Билли Холидей стала звездой.
Именно тогда Билли впервые исполнила песню, которая в дальнейшем всегда ассоциировалась с ее именем. Это песня на стихи поэта Льюиса Аллена, называлась она «Strange Fruit» («Странный плод»). Странным автор называл «черный плод, свисающий с черного дерева».
"Текст будущей песни Билли Холидей получила в 1939 году от поэта Льюиса Эллена, – пишет Д. Ухов. – Как возникла музыка к его стихам, до конца не установлено; не исключено, что ее написала сама певица. Но вот что интересно: солидная «Колумбия» в любом случае не стала бы связываться с песней остросоциального звучания. К тому времени, однако, певица уже смогла сама выбрать «компанию» – ею оказалась небольшая фирма «Коммодор». Билли Холидей записала «Странный плод» с тем же ансамблем, с которым выступала в кафе «Сесайети».