1935年～絶頂期
ジャズ・コンポーザーとして第一人者のデューク・エリントンは自身の映画「シンフォニー・イン・ブラック」にビリーを起用し、Saddest Tale （サディスト・テール）を歌わせその役を演じさせた。さらに、同時期にベンウェブスター（ｔｓ）とも共演を開始。ベンウェブスター（ｔｓ）、ベニー・グッドマン（クラリネット）、テディ・ウィルソン（ｐ）ジョン・トゥルーハート（ｂｓ）ジョン・カービー（ｄｓ）といった話題の人種混成バンドの共演をプロデューサーであるジョン・ハモンドが指揮をとりレコーディングを実現し「What a Little Moonlight Can Do （月光のいたずら） 」と「Miss Brown To You （ミス・ブラウン・トゥ・ユー） 」といった楽曲を演奏した。当時のベスト・メンバーである彼らの演奏は見事にその年のベストセラーに輝いた。この時期こそビリー・ホリデーの繁栄気であるといえる。その後もテディ・ウィルソンとコンビを組み、多くのアルバムを残すなどニューヨークの人気シンガーとしての地位を確立した。しかし、数多くのツアーをこなしながらも黒人である彼女の人種に対する差別は消えることはなく、地方巡業の先に於いても様々なトラブルを引き起こしたと言われている。