I suggest we go about learning the history of magic from a logistical standpoint. We cannot know, and will never know what truly happened at the beginning of magic. However, we can know what was most likely to have happened. 

What I believed to have happened at the start, is well, nothing. I don't believe there was a start or there ever will be an end to magic. Magic is a force, just like gravity, that has always existed around us. From the inception of the universe magic has been there, and there is most likely some form of alien wizardry that is similar to our own. 

I title this concept the Theory of Nothing. The theory states that magic is like anything we have discovered. Magic is almost like oxygen. Just because early creatures were unaware of it, doesn't mean it never existed. The history of magic starts at the beginning of the universe, but because Earth didn't exist at the start of the universe, we have no way to study the beginning of magic. However, what we can study is the beginning of witches and wizards.

The beginning of witches and wizards most likely starts with the earliest ancestor of the human, or the Australopithecus Afarensis. Other magical creatures could have possesed magic earlier, however, the ability to cast charms and brew potions most likely lied with the earliest ancestor of the human.

I title this concept Inglemoor's Theory. This theory states that as we know, the only wizards and witches are of the human species, or atleast partially. Because of this, we can logically deduce that if wizards and witches are of the human species, then the start of wizards and witches starts with the start of the human species. Early wizards and witches most likely did not know about their abilites, and were only able to conjure up accidental magic.