In 1493, known asshat Christopher Columbus arrived in America on his second expedition, this time bringing along a very special cargo, a bunch of horses. Given that horses had been extinct in the America's for over 10,000 years at that point, the native tribes naturally freaked the fuck out. Some even became convinced that the strange new white people must be gods, which seems a little strange given that though they were riding around some kind of magical animal, that magical animal was constantly shitting everywhere. Regardless, the Spanish used this confusion to their advantage, allowing them quickly spread across the Caribbean, South America, and Mexico.
By the end of the sixteenth century the Spanish had spread north as far as New Mexico where they enslaved the local Pueblo people. By this time the natives had abandoned the belief that the Spanish were gods, instead recognizing them as being just another group of assholes, but the horse still gave the Spanish a distinct advantage. Being assholes, but not morons, the Spanish had gone out of their way to keep horses and knowledge of how to ride them out of native hands. However, despite these attempts the secret slowly leaked out, largely due to various Spaniards teaching their enslaved Pueblo how to ride while others started selling horses to the various tribes. In 1680, tiring of the general shittiness of their situation, the Pueblo rebelled and started killing every Spaniard they could get their hands on. The Spanish retreated south leaving behind thousands of horses. The Pueblo, who were farmers at heart, mostly used their new horses for plowing and eating, but soon after also found a market in selling them north to other tribes.
At the time the tribes of the Great Plains and Great Basin were very different than how we picture them today. Most of the tribes were sedentary, mostly relying on farming where they could and hunting and gathering where they couldn't, and killing buffalo when they were nearby. The tribes at time did fight amongst each other, but mostly they kept to their own isolated areas. The introduction of the horse fucked all that up. The first two tribes to really embrace the horse were the Shoshone and Comanche. Relatively weak tribes who had often gotten the shit beat out of them by their stronger neighbors, the Shoshone and Comanche fully embraced the horse as a better way to hunt and wage war. Within a decade both had staked out wide territories across the western United States, killing anyone who dared stand in their way. Other tribes, seeing the success, began adopting similar methods, transforming the lifestyle of the entire Plains by 1770.
Prior to the widespread adoption of the horse, Plains tribes only had dogs to carry their shit around. The horse allowed for a much more nomadic lifestyle, with tribes ranging over a wider area searching for buffalo, which were basically giant treasure chests on legs. What followed was an economic boom which attracted more tribes into the area from both the east and west, with some tribes traveling as much as 1,000 miles each year to hunt buffalo. Formerly egalitarian societies splintered and became more about the obtainment of wealth with the richest men of the tribe claiming numerous wives and slaves. As well, the new wide ranging nomadic lifestyle meant that the tribes came into contact with each other much more often which of course led to increased violence and warfare over territories and resources. Many tribes became extremely militarized and numerous empires rose and fell over the decades. These warlike tribes halted the northward push by the Spaniards for most of the seventeenth century and westward push by the Americans for a good part of the nineteenth century.
Unfortunately it was all unsustainable. So many tribes were hunting buffalo on the Great Plains by the early 1800's that their numbers began to decline sharply. As well, the large herds of horses on the Plains caused widespread damage to areas due to overgrazing, the horse being one of the worse animals for such things. The situation became bad enough that the natives took to setting large prairie fires to encourage the increased growth of grass. What might have happened next will never be known. By the mid-nineteenth century the Americans were performing a full court press. Disease depleted the number of natives and war forced them into increasingly small territories. The final straw was the widespread slaughter of the buffalo in order to send the hides back east and to Europe for various products. By the end of the century they were nearly extinct. In a similar fashion, as the native tribes were increasingly wiped out, they left behind vast herds of wild horses across the Western United States. However, most of these were either rounded up and sold or slaughtered by the U.S. Army by the early twentieth century.