The problem was the horses were naturally smaller than the ones we artificially breed later.

So unless you happen to be in a place where horses are naturally big, you would look like a total idiot going around on a struggling pony that will have a broken back very soon.

Still totally possible there was an area where horses could grew stronger due to climate and people did profit of it way earlier. I mean, if 5000 years ago was possible, maybe it happen even earlier than 5000 year ago if there were big horses not man-breeded.