Horses were around when the first men reached this hemisphere along with a great deal of interesting megafauna. The Indians ate them until numbers were not sufficient to have a breeding population [and the mastadons and mammoths also suffered the same fate].
The most sensible theory I've seen blames the extinction of the megafauna on climate change, and not on depredations by humans. There simply weren't enough humans around to kill off all the mammoths etc. The only possible exception was the extinction of the New Zealand mega birds, and that only because of the limited range of New Zealand.
Also, the humans of the time were no more responsible for the changing climate than we are today. The earth's climate is a powerful and complex system, and much bigger than anything we can do. And besides, the temperature of Mars is climbing apace with the earth's? Are we responsible for "Martian Warming"?
Some tragedies of history are definitely the fault of humans (such as the introduction of feral cats into Australia and the invention of warm British beer). The extinction of the megafauna probably isn't one of them.