Playford Edition:

‘Hearts Ease’ can be located in the 1^st edition of The [English] Dancing Master, (1651). 

 Documentation prior to 1603:

‘Hearts Ease’ is mentioned in Act 4, Scene 5 of Shakespeare’s Romeo and Juliet, (1597).

“Peter: Musicians, O, musicians, Heart’s ease, Heart’s ease; O, an you will have me live, play Hearts ease.

Fiddler: Why Hearts ease?

Peter: O, musicians, because my hart itself plays My heart is full of woe; O, play me some merry dump, to comfort me.” ⁽¹⁾

For pictures of Hearts Ease being danced, click here.