"one time only; at one time in the past, formerly," c. 1200, anes, basically an adverbial form of one with adverbial genitive -s. The Old English form was æne, but it was replaced by, or reshaped by analogy with, the genitive singular of the early Middle English form of one and the common addition of -es to adverbs at that time. The spelling changed as pronunciation shifted from two syllables to one after c. 1300; the -ce is to retain the breathy -s- (compare hence). The pronunciation change to "wuns" parallels that of one.
As an emphatic, meaning "once and for all," it is attested from c. 1300, but in modern U.S. this is a Pennsylvania German dialect formation. Meaning "in a past time" (but not necessarily just one time) is from mid-13c.
Never once "never at all" is from early 13c. Once in a while "sometimes" is by 1781. Once upon a time as the beginning of a story is recorded from 1590s, earlier once on a time (late 14c.). 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. Once and for all "once as a final act" is from 1848, earlier once for all (late 15c.).