East of the Sun and West of the Moon is actually in the same classification as another annotated tale on this site: Beauty and the Beast. The tale is Aarne-Thompson tale type 425, "The Search for the Lost Husband." Beauty and the Beast is usually given its own subcategory as 425C which has the same name as the tale. East of the Sun and West of the Moon is usually placed in 425A: The Animal Bridegroom (Thompson 1945).
The tale of Cupid and Psyche (AT 425A) is considered by many scholars to be one of the first literary fairy tales. Written by Lucius Apuleius in the second century A.D., he relates the story in his novel, The Golden Ass, as an old wives' tale told by an older woman to a young woman who is being held hostage for ransom. The tale features many characters from Greek/Roman mythology, although earlier records of this tale are not known. Cupid and Psyche was translated into English in 1566 by William Adlington and was well-known throughout Europe. For example, John Milton refers to the story in his Comus, first performed in 1634 and published in 1637. You can read three versions of the tale on the Tales Similar to Beauty and the Beast Page. The tale is a direct ancestor of the French Beauty and the Beast tale. However, It bears even closer resemblance to East of the Sun and West of the Moon.
East of the Sun and West of the Moon was collected and recorded by the Norwegian folklorists, Peter Christen Asbjornsen and Jorgen Moe. They published it around 1845 in one of their first collections of tales. The tale had been previously popular in Scandinavian countries and then gained popularity in the United Kingdom and United states after the first English translation appeared in:
Montalba, Anthony R. Fairy Tales From All Nations. Richard Doyle, illustrator. London: Chapman & Hall,1849.
Please also read The History of Beauty and the Beast available through SurLaLune Fairy Tales.
