c. 1200, anes, from ane "one" (see one ) + adverbial genitive. Replaced Old English æne. Spelling changed as pronunciation shifted from two syllables to one after c. 1300. Pronunciation change to "wuns" parallels that of one. As an emphatic, meaning "once and for all," it is attested from c. 1300, but this now is regarded as a Pennsylvania German dialect formation. Meaning "in a past time" (but not necessarily just one time) is from mid-13c.
Once upon a time as the beginning of a story is recorded from 1590s. At once originally (early 13c.) meant "simultaneously," later "in one company" (c. 1300), and preserved the sense of "one" in the word; the phrase typically appeared as one word, atones; the modern meaning "immediately" is attested from 1530s.