The horse is central to many Indigenous cultures across the American Southwest and the Great Plains. However, when and how horses were first integrated into Indigenous lifeways remain contentious, with extant models derived largely from colonial records. We conducted an interdisciplinary study of an assemblage of historic archaeological horse remains, integrating genomic, isotopic, radiocarbon, and paleopathological evidence. Archaeological and modern North American horses show strong Iberian genetic affinities, with later influx from British sources, but no Viking proximity. Horses rapidly spread from the south into the northern Rockies and central plains by the first half of the 17th century CE, likely through Indigenous exchange networks. They were deeply integrated into Indigenous societies before the arrival of 18th-century European observers, as reflected in herd management, ceremonial practices, and culture.