Etymology of "history" and why the "hi-" prefix?

If you look more closely you will see that the hi- was there originally, in Greek historia from which it was borrowed into Latin. The initial syllable was weakened and sometimes dropped in Late Latin, and reduced to e- in Old French, from which the word was borrowed into Middle English.

In ME it shows up as historie, istorie, estorie and histoire, all representing OF forms, probably influenced by Latin – for of course Latin was still a living written language of learning and scholarship. Alongside these a “native” version, with the initial syllable entirely dropped, began to show up; this appears as storie, stor, storri, with plurals stories, storise, storius, and storien.

All these forms were used indifferently for any narrative account, whether formal chronicle or patent romance. It was not until Early Modern English – the 16th century – that spellings and forms began to shake down– probably, again, influenced by the status of Latin as the principal language of learning – into the contrasting history = factual narrative and story = fictional narrative.

Note that to this day French histoire means both story and history – as does the corresponding term in German, Geschichte. I imagine this is true in many other European languages.

EDIT:
This simplified contrast is rightly challenged by Arlen Beiler and John Lawler: story embraces any narrative, not only fictional narratives, and the two terms have never completely separated. But by and large, history has come to mean the product of the academic discipline, while story has come to mean an engrossing narrative. OED 1 puts it rather neatly, I think, under Story 4 e [story of a life, institution, etc. ]:

Originally = HISTORY 4 b; but in modern use (from association with Sense 5) implying that the course of events referred to has the kind of interest which it is the aim of fiction to create.

I must also acknowledge that over the past two generations historiographers have grown skeptical of the Rankean eigentlich gewesen and are much more conscious of the element of mythopoesis in their work; so in a sense history is collapsing back into story.