Rani život i teško djetinjstvo
Punog imena Eleanora Fagan Gough, Holiday je rođena 7. travnja 1915. U Philadelphiji, a veći je dio svog djetinjstva provela u Baltimoreu. Njezina majka Sadie bila je tek tinejdžerica kad ju je rodila, a odrasla je bez oca Clarencea Holidaya, uspješnog jazz glazbenika koji je svirao gitaru uz Fletchera Hendersona. Zbog teškog djetinjstva, Holiday je ubrzo počela izostajati iz škole, zbog čega je u siječnju 1925. poslana u Kuću dobrog pastira, ustanovu za problematične afroameričke djevojke, u dobi od samo devet godina. U kolovozu iste godine vraćena je na majčinu skrb, no 1926. vratila se u ustanovu nakon što je bila seksualno zlostavljana.
U svom teškom ranom životu, Holiday je utjehu pronašla u glazbi, pjevajući uz ploče Bessie Smith i Louisa Armstronga. Pratila je svoju majku, koja se krajem 1920-ih preselila u New York, i jedno vrijeme radila u javnoj kući u Harlemu. Oko 1930. Holiday je počela pjevati u lokalnim klubovima i preimenovala se u "Billie" po filmskoj zvijezdi Billie Dove.