Old English mægden, mæden "unmarried woman (usually young); virgin; girl; maidservant," diminutive of mægð, mægeð "virgin, girl; woman, wife," from Proto-Germanic *magadin- "young womanhood, sexually inexperienced female" (source also of Old Saxon magath, Old Frisian maged, Old High German magad "virgin, maid," German Magd "maid, maidservant," German Mädchen "girl, maid," from Mägdchen "little maid"), fem. variant of PIE root *maghu- "youngster of either sex, unmarried person" (source also of Old English magu "child, son, male descendant," Avestan magava- "unmarried," Old Irish maug "slave").
Also in Middle English "a man lacking or abstaining from sexual experience" (c. 1200). As the name of a guillotine-like instrument of execution by beheading, from 1580s.
c. 1300, "virgin, unmarried," from maiden (n.). The figurative sense of "new, fresh, untried; first" (as in maiden voyage) is by 1550s. In horse-racing (1760) it denotes young horses that have never run before. Maiden name "family name of a woman before her marriage" is from 1680s.