A história de Billie Holiday e do saxofonista Lester Young não foi moldada em conjunto. Talvez o melhor momento de cada um tenha sido registrado quando estavam bem distantes um do outro, mas é impossível não se espantar diante da colossal cumplicidade e entrosamento entre os dois. Entre a segunda metade dos anos 30 e durante vários períodos dos anos 40 e 50, Young e Holiday dividiram o palco e o estúdio de gravações.

- Billie Holiday/Lester Young - "A Sailboat In The Moonlight" (Lombardo/Loeb)
- Billie Holiday/Lester Young - "He's Funny That Way" (Daniels/Whiting)
- Billie Holiday/Lester Young - "Getting Some Fun Out Of Life" (Leslie/Burke)
- Billie Holiday/Lester Young - "Without Your Love" (Burke/Leslie)
- Billie Holiday/Lester Young - "Me, Myself and I" (Gordon/Kaufman/Roberts)
- Billie Holiday/Lester Young - "He Ain't Got Rhythm" (Irving Berlin)
- Billie Holiday/Lester Young - "I Must Have that Man" (Fields/McHugh)
- Billie Holiday/Lester Young - 'I'll Never B The Same" (Kahn/Malneck/Signorelli)
- Billie Holiday/Lester Young - "Mean To Me" (Turk/Ahlert)
- Billie Holiday/Lester Young - 'If Dreams Come True" (Goodman/Sampson/Mills)
- Billie Holiday/Lester Young - 'This Year's Kisses" (Irvin Berlin)
- Billie Holiday/Lester Young - "All Of Me" (Marks/Simons)
- Billie Holiday/Lester Young - "The Man I Love" (George e Ira Gershwin)
- Billie Holiday/Lester Young - "'Tain't Nobody's Business If I Do" (Grainger/Robins)
- Billie Holiday/Lester Young - "Baby Get Lost" (Leonard Feather)
- Billie Holiday/Lester Young - "Fine and Mellow" (Billie Holiday)

Holiday e Young estiveram juntos na orquestra de Count Basie, registraram gravações com a orquestra do pianista Teddy Wilson ou quando a banda era comandada pela própria Holiday.
A abordagem melancólica, traçada por um viés autodestrutivo, refletia em interpretações encantadoras. Holiday e Young não rodeavam a harmonia apenas com notas matematicamente bem encaixadas, mas interpretavam as composições até encontrar algum sentido para tal. Os dois transportaram clássicos do jazz para outra dimensão, deixando para seus discípulos a desanimadora sensação de que não havia mais novos caminhos a seguir.
Young tratava o sax tenor com tanta leveza que até mesmo durante o manejo do instrumento levantava-o para a direita, tratando-o como uma graciosa flauta transversal. Delicado, Lester chamava Holiday de 'Lady Day', que, em contrapartida, batizou o amigo de 'Pres', o presidente.
Os dois morreram em 1959. Lester, em março, aos 49 anos, vítima do excesso de álcool. Holiday, que em relação ao vício pelas drogas não deixava por menos, chegou a dizer no enterro de Lester que 'seria a próxima'. Em julho, Holiday morreu aos 44 anos.