Genetic research found that horses evolved in North America millions of years ago and spread to Asia and Europe before dying out in the Americas 6,000 years ago.

Then in the early 1600s they were back, brought by Europeans, according to a new study.
Some stories claimed that natives only got horses after the Pueblo Revolt of 1680 , when Spanish were defeated in New Mexico and left those and livestock.

The new work shows that a trading network had already provided horses decades early, but with some 900 native tribes who got them from the Spanish will remain unclear. Some contend they had run away from camps and didn't directly involve dealing with the Spanish at all, that remains the problem with oral tradition instead of developing writing. That can be left to cultural scholars, the science shows that, over time, British horses entered the genetic mix, showing the change in power.

It's interesting to me that the Old West of romantic stories is now seen as white "Cowboys" and native "Indians", when it was primarily the Spanish, then black people joined in herding on horseback, then natives, and whites last. Horses and hats were consistently in the picture the entire time.