According to Ellington scholar A.H. Lawrence, the composition originated as a solo piano piece titled "Firewater" that Ellington played at the Cotton Club at the end of intermissions, as his band members returned to the stage.
He renamed the piece "Black Beauty" and dedicated it to singer, dancer, and comedian Florence Mills, who had died the previous year.
Sixth months later, Ellington recorded a solo piano version for the OKeh label.
Ellington recorded the song in the studio on several later occasions, the last being a small group version made for the Columbia label in 1960.
Ellington's original orchestrated version has a more upbeat tempo, similar to his late-1920s hits, though later band arrangements abandoned this approach.