Ælfric, in his Old English glossary, defines the Latin word unicornis (although, being a glossary, I'm not sure this counts for the purpose of the question):
unicornis anhyrne deor; þæt deor hæfð ænne horn bufan ðam twam eagum swa strangne and swa scearpne, þæt he fyht wið ðone mycclan ylp and hine oft gewundað on ðære wambe oð deað. He hatte eac rinoceron and monoceron.
My translation:
Unicornis, one-horned deer; that deer has one horn above the two eyes so strong and so sharp, that he fights with the great elephant and [the elelphant is] oft wounded on the belly until dead. He is also called rinoceron and monoceron.
The first work to use "unicorn" in English, according to the Oxford English Dictionary, is Ancrene Riwle, probably written before 1200, although the earliest manuscripts are circa 1225. The original says:
Wummon wrað is wuluene; Mon wulf oðer liun oðer unicorne.
I found a translation of this online which gives the context more fully:
An angry woman is a she-wolf, and an angry man is a wolf, or a lion, or a unicorn.
[...] Go, however, very cautiously: for in this wilderness there are many evil beasts – the lion of pride, the serpent of venomous envy, the unicorn of wrath, the bear of dead sloth, the fox of covetousness, the swine of greediness, the scorpion with the tail of stinking lechery, that is, lustfulness. These, now, are the seven chief sins detailed in order.
[...] The Unicorn of Wrath, which bears on his nose the horn with which he butts at all whom he reaches, has six whelps. The first is Contention or Strife. The second is Rage. The third is contumelous Reproach. The fourth is Cursing. The fifth is Striking. The sixth is Wishing that Evil may happen to a man himself, or to his friend, or to his possessions.
[...] Of those seven beasts, and of their offspring in the wilderness, and of a solitary life, we have spoken thus far – which beasts are endeavouring to destroy all mortals. The Lion of Pride slays all the proud, and all those who are elated and lofty in heart The venomous serpent [slays] all the envious, and all who have base malicious thoughts. The Unicorn, all the wrathful; and so of the others in succession.
Although it's an educational metaphor, I think it still counts as a story.