c. 1300, fairie, "the country or home of supernatural or legendary creatures; fairyland," also "something incredible or fictitious," from Old French faerie "land of fairies, meeting of fairies; enchantment, magic, witchcraft, sorcery" (12c.), from fae "fay," from Latin fata "the Fates," plural of fatum "that which is ordained; destiny, fate," from PIE root *bha- (2) "to speak, tell, say." Also compare fate (n.), also fay.

In ordinary use an elf differs from a fairy only in generally seeming young, and being more often mischievous. [Century Dictionary]

But that was before Tolkien. As a type of supernatural being from late 14c. [contra Tolkien; for example "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" (c. 1300), as in Spenser, where faeries are heroic and human-sized. As a name for the diminutive winged beings in children's stories 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]

Hence, figurative adjective use in reference to lightness, fineness, delicacy. Slang meaning "effeminate male homosexual" is recorded by 1895. Fairy ring, of certain fungi in grass fields (as we would explain it now), is from 1590s. Fairy godmother attested from 1820. Fossil Cretaceous sea urchins found on the English downlands were called fairy loaves, and a book from 1787 reports that "country people" in England called the stones of the old Roman roads fairy pavements.