"Heart of Stone" is a song performed by Taylor Dayne, released as the fourth and final single from Dayne's second album, Can't Fight Fate. The single performed better in the U.S. Adult Contemporary charts than it did in the pop charts. Dayne delivers her vocals in a soft engaging manner. The song is co-written by Elliot Wolff, responsible for Paula Abdul's number-one single "Straight Up".
The music video was included in Dayne's music video collection Twist of Fate.
This single broke Dayne's streak of seven consecutive U.S. Top 10 singles on the Billboard Hot 100, reaching number 12.