1530s, "freedom from exaggeration, self-control," from French modestie or directly from Latin modestia "moderation, sense of honor, correctness of conduct," from modestus "moderate, keeping due measure, sober, gentle, temperate," from modus "measure, manner" (from PIE root *med- "take appropriate measures"). Meaning "quality of having a moderate opinion of oneself, retiring demeanor, disinclination to presumption, unobtrusiveness" is from 1550s; that of "womanly propriety, purity or delicacy of thought or manner" is from 1560s.
In euery of these thinges and their semblable is Modestie; whiche worde nat beinge knowen in the englisshe tonge, ne of al them which under stode latin, except they had radde good autours, they improprely named this vertue discretion. [Sir Thomas Elyot, "The Boke Named The Gouernour," 1531]
La pudeur donne des plaisirs bien flatteurs à l'amant: elle lui fait sentir quelles lois l'on transgresse pour lui;(Modesty both pleases and flatters a lover, for it lays stress on the laws which are being transgressed for his sake.) [Stendhal "de l'Amour," 1822]
The pride which masks as modesty is the most perverse of all. [Marcus Aurelius]
Middle English pratie "cunning, crafty, clever" (c. 1300 as a surname), from Old English prættig (West Saxon), pretti (Kentish), *prettig (Mercian) "cunning, skillful, artful, wily, astute," from prætt, *prett "a trick, wile, craft," from Proto-Germanic *pratt- (source also of Old Norse prettr "a trick," prettugr "tricky;" Frisian pret, Middle Dutch perte, Dutch pret "trick, joke," Dutch prettig "sportive, funny," Flemish pertig "brisk, clever"), a word of unknown origin.
The connection between the Old English and Middle English words "has several points of obscurity" [OED], and except in surnames there is no record of it 13c.-14c., but they generally are considered the same. The meaning had expanded by c. 1400 to "manly, gallant," also "ingeniously or cleverly made," to "fine, pleasing to the aesthetic sense," to "beautiful in a slight way" (mid-15c.). Also used of bees (c. 1400). For sense evolution, compare nice, silly, neat (adj.), fair (adj.).
Pretty applies to that which has symmetry and delicacy, a diminutive beauty, without the higher qualities of gracefulness, dignity, feeling, purpose, etc. A thing not small of its kind may be called pretty if it is of little dignity or consequence: as a pretty dress or shade of color; but pretty is not used of men or their belongings, except in contempt. [Century Dictionary, 1897]
Of things, "fine, pleasing" 1560s. Ironical use is from 1530s (compare ironical use of fine (adj.)). The meaning "not a few, considerable, moderately large in quantity, number, extent, or duration" is from late 15c. Pretty please as an emphatic plea is attested from 1902. A pretty penny "lot of money" is recorded from 1703.
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.