The story
Uncertain, possibly related to take heart (“to be courageous; to regain one’s courage”). It is unclear whether the original term was heart of grace, or perhaps hart of grace, heart of grease or hart of grease (“hart of the season when fat”), or hart (heart) of grass (perhaps alluding to a horse taking heart when finding grass), and of is sometimes replaced by at. Later uses have been influenced by grace (“free and undeserved favour”).
Etymology from Wiktionary, CC BY-SA 4.0.