"Heart of Stone" was originally recorded by Bucks Fizz and released as a single in 1988. It was the group's 20th single and their last one to chart, reaching number 50 on the UK Singles Chart in November 1988. The single was accompanied by a Promotional video of the group performing the song inside and outside of a country mansion. The mansion was owned by Robin Gibb of the Bee Gees who claimed that his house was haunted by the ghost of a gardener who enjoys playing pranks on the Gibb family. As a reference to this, a gardener was fleetingly seen in some shots.
Soon after this, the group released The Story so Far, a greatest hits album, which featured "Heart of Stone" as the only new track (at a shortened 3:58). Bucks Fizz recorded several other songs at this time, but due to the low chart position of this single, went unreleased until they were unearthed for a compilation album of unreleased Bucks Fizz songs, The Lost Masters in 2006. Member Cheryl Baker later recorded a lead vocal for the track which was also included on The Lost Masters collection. Journalist Mark Frith said that the song was "a gusty pop classic".
"Heart of Stone" is the fourth North American and third Europeansingle release from American singer/actress Cher's twentieth studio album Heart of Stone. The video featured Cher in a dark room with old clips of herself projected onto screens in the background. The video was shot in the first week of 1990. It made the Top 20 in the United States, Ireland and Poland. It narrowly missed the Top 40 in the UK. Her vocal range spans from a D3 and belting up to an Eb5, making her vocal range here about 2 octaves and a semi-tone.