This expression and similar are found under definition 8a(g) in the MED:
in phrases freq. introducing a narrative: ones on a time, in (on, upon) a time, in (on) on time, etc., once upon a time, once; also, in adv. constructions without prep.: o (on) time, on a certain occasion, once
Coincidentally, you can also see "on a time" in this free OED page.
One of the first examples is from
c1225(?c1200) from Þe Liflade of St. Juliana. Although it's only in the third paragraph, it still serves to start off the rest of the story:
Wes iþon [Roy: bi þon] time as þe redunge telleð þe modi Maximien keiser irome...
This translates as:
In that time, as the legend tells, the proud emperor Maximian was in
St. Katherine also from circa 1225 has a similar line:
Constantin ant Maxence weren on ane time [c1225 Bodl. on a time] as in keiseres stude hehest irome.
Which translates (according to me) as:
Constantine and Maxentius were on a time...
There's also Speculum Guy, c1330:
A tale i wole ȝou telle Off an eorl..Gy of Warwyk was his name, Hou on a time he stod in þouht.
A tale I wish to tell you of an earl... Guy of Warwick was his name, how on a time he stood in thought. (translation mine)
Chaucer, in his Knight's Tale, uses the wording "ones on a time", but this happens in the middle of the story.
It seems the wording with upon came later:
Galien seith and tellith þat vp-on a tyme he sey a child þat had þe fallyng evell.
Galien says and tells that upon a time he... (translation mine)
A Middle English Translation of Macer Floridus de Viribus Herbarum, a1450
Also related is "once upon a day", which dates back to circa 1380:
Onys..oppon a day..he slow kynges three.