"Hey!" has been in constant use since at least the 13th century (according to OED 1 the earliest documentation is 1225, but identical expressions occur in several other Germanic languages). It's an interjection expressive of, well, practically anything you get excited about, much as it is today: "Hey, you!" "Hey! What a party!" "Hey-hey-hey!"
An 'intensive' variant, "Heyda" (also with continental cognates), is first recorded in 1526, in this eloquent cry uttered by Courtly Abusyon in Skelton's *Magnyfycence":
Huffa huffa taunderum taunderum tayne huffa huffa
[...] Rutty bully, ioly rutterkyn, heyda!
—an obvious antecedent of Cab Calloway's Minnie the Moocher, who sang:
By the end of the century the word is pronounced 'hayday'. It has also acquired a nominal sense: the high spirits (especially erotic high spirits) which move someone to cry "Heyda!" For instance, Hamlet reproaches his mother's unseemly sexuality thus:
You cannot call it love, for at your age
The hey-day in the blood is tame, it's humble,
And waits upon the judgment.
And Ford writes (1633):
Must your hot itch and pleurisy of lust
The heyday of your luxury be fed
Up to a surfeit?
Something very similar happened in the last century to the old interjection "hoppla" or "whoopee", which evolved into "making whoopee".
This nominal sense seems to have died out of colloquial use in the 18th century, to the extent that the last syllable was no longer understood and was taken to have something to do with "day"; consequently (and perhaps under the influence of Shakespeare's line) a sort of reverse folk-etymology shifted the sense of the noun to
"the stage or period when excited feeling is at its height [...] the most flourishing or exalted time" (OED)
which is the sense it bears today.