mid-14c., contraction of Old English phrase ealne weg "all the time; quite, perpetually," literally "all the way," with accusative of space or distance, though the oldest recorded usages refer to time; see all + way (n.). The adverbial genitive -s appeared early 13c., was rare before c. 1400, but is now standard, though the variant alway survived into 1800s. Meaning "every time" is from early 13c.