c.1300, fairie, "enchantment, magic," from Old French faerie "land of fairies, meeting of fairies, enchantment, magic," from fae "fay," from Latin fata (plural) "the Fates," from PIE *bha- "to speak" (see fame (n.)).
As "a supernatural creature" from late 14c. [contra Tolkien; cf. "This maketh that ther been no fairyes" in "Wife of Bath's Tale"], perhaps via intermediate forms such as fairie knight "supernatural or legendary knight" (early 14c.). The diminutive winged beings so-called in children's stories seem to date from early 17c.
Yet I suspect that this flower-and-butterfly minuteness was also a product of "rationalization," which transformed the glamour of Elfland into mere finesse, and invisibility into a fragility that could hide in a cowslip or shrink behind a blade of grass. It seems to become fashionable soon after the great voyages had begun to make the world seem too narrow to hold both men and elves; when the magic land of Hy Breasail in the West had become the mere Brazils, the land of red-dye-wood. [J.R.R. Tolkien, "On Fairy-Stories," 1947]The slang meaning "effeminate male homosexual" is first recorded 1895. Fairy ring is from 1590s. Fossil sea urchins found on the English downlands were called fairy loaves.