"King Henry" is a retelling the Beauty and the Beast story, the only difference being that the sexes are reversed. The most common use of this motif in folk tales is the Loathly Lady. The motif is that of a woman that appears unattractive (ugly, loathly) but undergoes a transformation upon being approached by a man in spite of her unattractiveness, becoming extremely desirable. It is then revealed that her ugliness was the result of a curse which was broken by the hero's action.
In Irish tales Niall of the Nine Hostages proves himself the rightful High King of Ireland by embracing a Loathly Lady. Several other tales feature the hag or Loathly Lady as representing the sovereignty of Ireland. In Arthurian literature the best known treatment is in the Wife of Bath's Tale, in which a knight, told that he can choose whether his bride is to be ugly yet faithful, or beautiful yet false, frees the lady from the form entirely by allowing her to choose for herself. The theme also appears in The Marriage of Sir Gawain and in Wolfram von Eschenbach's romance Parzival. The Loathly Lady also appears in the Old Norse Hrólfr Kraki's Saga.
It is #32 in F. J. Child's The English and Scottish Popular Ballads and appears as #3967 in The Roud Folk Song Index.
It was recorded by Steeleye Span and, separately, by Martin Carthy and others.
I learned it from the recording by Steeleye Span.