Horses went extinct in North America at the end of the Pleistocene (about 12,000 years ago). They didn't return to the Americas until Europeans arrived. While small numbers of horses escaped or were targeted specifically for capture in conflicts between various European and Native nations throughout the colonial period, the major turning point on the Great Plains came in 1680. The Pueblo Revolt ended nearly 70 82* years of Spanish occupation in New Mexico, and drove the Spanish frontier south for about a decade. Throughout New Mexico, the Spanish had trained local people to care for their horses, and now that the locals were back in charge, they could do what they pleased with those horses. Large numbers were sold off to people on the southern Plains, such as the Comanche who had recently come down from the north. Through raiding and trading, horses spread northward through the Plains, so by the early 1800s - when the United States claimed the Plains through the Louisiana Purchase - the vast majority of Plains cultures had adopted the horse and undergone considerable social shifts to maximize their usefulness. The Lakota, for example, were semi-sedentary hunters and farmers before the horses showed up and allowed them to follow bison herds regularly.

*I was thinking the Spanish conquest of New Mexico was in in 1608; it's actually 1598.