Billie Holiday is an unreleased track, thought to have been recorded in mid-September 1988, at Paisley Park Studios in Chanhassen, Minnesota (in the four-day break between European and North American legs of the Lovesexy Tour). Prince recorded keyboard overdubs on 25 September 1988, also at Paisley Park Studios (during two days off from the Lovesexy Tour, on the same day as recording vocal overdubs on The Rock That Keeps Rolling and compiling an early configuration of the Graffiti Bridge album, four days before recording Come Back 2 Me).
It was intended for the Graffiti Bridge movie, and Billie Holiday was one of the names written on the "graffiti bridge" in an early script (along with John Lennon, Martin Luther King, Jr., and Jesus Christ). It was named after Billie Holiday, the American jazz singer-songwriter who found great success in the 1930s-50s, but the lyrics are not known. It was not included on any known configuration of the Graffiti Bridge album, however, and the track remains unreleased.