Melody Cool was the fourth single to be released from Prince’s twelfth album Graffiti Bridge, although, like the song Melody Cool, the single was credited only to Mavis Staples (Melody Cool was later included, in a slightly different mix, on Staples' 1993 album The Voice).
The single was released three and a half months after the album, although in Europe it had been released in August. Melody Cool was featured in the movie Graffiti Bridge, which had been released a few months prior.
The b-side, Time Waits For No One, was taken (in edited form) from Mavis Staples' 1989 album Time Waits For No One, and the single also contained remixes of the title track.
The single reached number 36 on the US Billboard R&B Chart, but failed to enter the Billboard Pop Chart.