c. 1300, "freed from dregs or lees" (of ale, wine, etc.), probably literally "having stood long enough to clear," from Old French estale "settled, clear," from estal "place, fixed position," from Frankish *stal- "position," from Proto-Germanic *stol-, from PIE root *stel- "to put, stand, put in order," with derivatives referring to a standing object or place.
Cognate with Middle Dutch stel "stale" (of beer and old urine). Originally a desirable quality (in beer and wine); the meaning "not fresh" is first recorded late 15c. Figurative sense (of immaterial things) "old and trite, hackneyed" is recorded from 1560s. As a noun, "that which has become tasteless by exposure," hence "a prostitute" (in Shakespeare, etc.). Related: Staleness.