I think it's something that just came with necessity when humans first started forming tribes and communities. Obviously some kind of laws, no matter how primitive, had to be established in order for them to exist for a long period of time. That in itself is probably the foundation for morality.
But honestly, I don't see morality as being a natural thing. It's a human concept. If you look to the wild, to nature, well, there isn't much morality to be found at all. It's incredibly vicious, driven by the instinct to survive. We see this in the universe as well, with stars dying and their systems being destroyed (and in the process, any living thing within). Everything that is natural tends to be pretty damn destructive, or for its own personal benefit (though of course unintended positive side affects do happen, such as bees pollinating flowers).
I think if we looked back far enough, before civilisation, humans may have acted as animals, behaving purely by instinct with morality coming later.
Of course I could be wrong, but it makes sense to me.