Va començar en la música l'any 1934 com a ballarina de la tropa del Cotton Club, famós cabaret de Harlem on és la cantant tres anys més tard, acompanyada per l'orquestra de Charlie Barnet.[6] Lena Horne a continuació destaca a Broadway i comença una carrera cinematogràfica.
Després un fals inici en un film musical parlat de 1938, titulat The Duke is Tops, Horne és la primera dona afroamericana que signa un contracte de llarga durada amb un estudi de Hollywood, la Metro-Goldwyn-Mayer (MGM). Comença l'any 1942 a Panama Hattie i és famosa el 1943 per la interpretació de Stormy Weather al film del mateix nom. Apareix a continuació en nombroses comèdies musicals de la MGM, tanmateix no tindrà gaires primers papers pel seu color de pell, per por del boicot als Estats del Sud, on els cinemes rebutjaven projectar aquests films. L'única excepció notable és Cabin in the Sky (1943), encara que una de les parts del seu cos es va tallar perquè era considerat com massa suggestiu pels censors. Havia de fer el paper de Julia LaVerne en la versió de 1951 de Show Boat que va caure finalment a Ava Gardner.
Horne es va casar amb Lennie Hayton, un jueu americà. Hayton és un dels primers caps d'orquestra arranjadors de la MGM. El matrimoni perdura fins a la mort de Hayton el 1971, en un entorn hostil. En efecte, els directors executius dels estudis desaproven aquesta unió interracial i la parella és bandejada. En la seva biografia coescrita amb Richard Schickel, Horne explica les grans pressions i les injúries que els fan patir.
Als anys cinquanta del segle xx, la parella és acusada d'«activitats anti-americanes», cosa que va resultar per a Lena Horne en una travessa del desert esmaltada d'alguns discos que arriba a gravar per la RCA.[1] És el 1957, i gràcies a la revista Jamaica, que torna amb l'èxit. Encadenarà amb rodatges i un cert nombre de revistes fins als anys 1970.
Torna als anys 1990 amb dos àlbums gravats per la discografia Blue Note.