De família negra pobra, tingué una infantesa inestable i difícil. Als catorze anys abandonà l’escola i el 1933 debutà al Cotton Club (cèlebre local musical de Nova York conegut sobretot per les actuacions de l’orquestra de Duke Ellington i Cab Calloway) com a ballarina i cantant. Posteriorment actuà també en teatres de Broadway, i el 1938 en el primer musical, The Duke Is Tops (1938), de W.L. Nolte, a la qual seguiren Cabin in the Sky (1943), de V. Minnelli, Stormy Weather (1943), d’A. L. Stone, Broadway Rhythm (1944), de R. del Ruth i Till the Clouds Roll By (1946), de R. Whorf.
Tot i les seves aptituds, la seva carrera cinematogràfica restà frustrada pels prejudicis racials de l’època (es nega, per exemple, a interpretar criades o personatges servils, papers als quals eren destinats majoritàriament els actors negres), i posteriorment només actuà en el western Death of a Gunfighter (1969) i el musical The Wiz (1978), de S. Lumet, bé que feu aparicions com a cantant en nombroses films.
Es concentrà en el teatre musical, activitat en la qual aconseguí un ampli reconeixement, del qual són mostres els espectacles Jamaica (1957, que obtingué un premi Tony), Lena in Concert (1969) i Lena Horne: The Lady and Her Music (1981, que guanyà un segon Tony i dos premis Grammy). Enregistrà també nombrosos discs, i el 1989 guanyà un Grammy a la trajectòria.
Després d’un primer matrimoni (1937-44), del qual tingué dos fills, el 1947 es casà amb el director d’orquestra Lennie Hayton, matrimoni que mantingué en secret alguns anys per ser interracial. Els anys seixanta participà molt activament en la lluita per la igualtat de drets dels negres nord-americans.