Melody Cool is the 14th track on Prince's twelfth album Graffiti Bridge (the first and only track on the album to be credited to Mavis Staples), and, around a month after the album's release, Melody Cool was released as the album's third single (the only single from the album credited to Mavis Staples). The extended version of the track was also included on the European CD single of New Power Generation by Prince, the album's fourth single. The track is also featured in the movie Graffiti Bridge. In 1993, it was also included in a slightly different mix as the seventh track on Mavis Staples' second Paisley Park Records album The Voice (included as the twelfth track on the 1995 NPG Records re-release).
Basic tracking on 9 July 1987 during Prince's first recording sessions at Paisley Park Studios in Chanhassen, Minnesota (on the same day as No Changes, two days before Graffiti Bridge and overdubbing on Big Tall Wall and around the time of a re-recording of If I Love You Tonight, now titled If I Love U 2 Nite). Melody Cool marks the earliest recording from Paisley Park Studios to be released, therefore, although Prince's original vocals were replaced by Mavis Staples. The original 1987 version also featured some lyrical differences, and the song was sung from a third-person perspective ("they call her Melody Cool"). This original version was included as the eighth track on a 25 September 1988 configuration of Graffiti Bridge. It was also included on a configuration of the Rave Unto The Joy Fantastic album, dated 27 October 1988 (segueing from The Voice Inside), but was removed for the late 1988 - early 1989 configuration. It was included as the eleventh track on a late 1989 configuration of Graffiti Bridge. At some point, most likely in late 1989, Prince recorded a guide vocal for Mavis Staples, using the first-person perspective of the lyrics for her to overdub; it is likely that further musical changes took place on the track at the same time. Mavis Staples recorded vocal overdubs onto the track in late 1989 or early 1990, and the track in its released form was included as the 13th track on a 1990 configuration of the album. The track switched places with The Latest Fashion to become the 14th track on the final release.
The movie Graffiti Bridge was developed starting in September 1987, indicating that the character Melody Cool in the movie, played by Mavis Staples, was conceived to some degree before the movie itself.