I found some earlier less exact matches than some others here, and while not technically answering the question regarding the exact phrase "happily ever after", the question may not actually be more definitively answerable than pointing at the earliest known attestation (already posted), so I am posting these, as they may give clues as to how the phrase settled to the "happily ever after" form.
This one is pretty close, coming after peace was restored to a household through servants being whipped for telling rumors concerning the lady of the house:
...they lived ever after with a most memorable sweetnesse of mutuall courtesies.
-- From Saint Augustines Confessions Translated: ᴀɴᴅ With some Marginall Notes illustrated by William Wats (1650 -- Google Books' "About this book" page says 1550, but the title page says "M.DC.L."), p. 283.
Perhaps arguing against the suggestion in some comments above that the exact "happily ever after" form may have began due to translation of works in other languages, is the fact that both the phrases "lived happily" and "ever after" existed before in English, and similar full statements with the same overall meaning had precedent in original English works even before it got jelled into the familliar phrase:
And this agreement thus made, and in a Parliament at Winchester confirmed, Duke Henry ever after accounted King Stephen no less then a Father; and King Stephen: Duke Henry no less then a Son, and well he might, if it be true which some write, that the Emperess, when a Battel was to be fought between King Stephen and her Son, went privily to him, asking him how he could finde in his heart to fight against him that was his own Son? Could he forget the familiarity he had with her in her Widow-hood! But this was no matter for the Writers of that time to deliver. It touched too near the Interest of Princes then in being, and Princes must not be touched while they live; nor when they are dead neither, with uncertainties, as this could be no other: But howsoever it was, certain it is, that after this agreement between King Stephen, and Duke Henry, they continued in mutual love and concord, as long after as they lived.
-- From A Chronicle of the Kings of England, from the Time of the Romans Government Unto the Death of King James (1670), p. 49. (Italicization original, bold added.)
...for they loved well their Lords the Romans, under whose government they lived happily.
-- From *The Historie of the World: In Five Bookes" by Walter Raleigh (1614), p. 396.
To which I yeelded for quietnesse and unity sake, and ever after lived peaceably, contentedly, and friendly together, the Captain denying me nothing; yea, tendring me more courtesie then I desired, or would accept of.
From A True Declaration of the intollerable wrongs done to Richard Boothby, Merchant of India, by two lewd servants to the honorable East India Company, Richard Wylde, and George Page. As also a remonstrance of the partiall, ingratefull and unjust proceeds of the India Court at home, against the said Richard Boothby, etc (1644), p. 21
And at the end of the story *The Tale of a Traveller:
...married they were, and in a short time after he carried her to his House, there made her Mistress of his Estate; and whilst he governed his outward Affairs, she governed the Family at home, where they lived plentifully, pleasantly, and peaceably; not extravagantly, vain-gloriously, and luxuriously; they lived neat and cleanly, they loved passionately, thrived moderately; and happily they lived, and piously dyed.
-- From Natures Pictures drawn by Fancies Pencil to the Life (1671) p. 544.
That's not the only tale in that book have an ending of that sort; on p. 514, at the end of the tale Assaulted and Pursued Chastity, which takes place in mythical kingdoms:
and the two Kingdoms lived in Peace and Tranquillity during the life of the King and Queen; and, for ought I can hear, do so to this day.