The Upland Pai are descendants of the prehistoric Cerbat tradition, inhabiting the present territory of the Pai as early as AD. 1100. The Walapai origin myth places the creation of all the Yuman groups at a place on the west bank of the Colorado River, where the Great Spirit transformed the canes along the river's edge into humans. Although Spanish explorers and missionaries established relations with the Yumans living along the river in the sixteenth and seventeenth centuries, it was not until 1776 that direct and brief contact with Walapais occurred.
They remained isolated for another seventy years, until the U.S. Army began to sponsor the search through northern Arizona for railroad routes to the West Coast. These explorations initiated two decades of hostilities between the Walapai and Anglos—the soldiers and the settlers who followed closely behind them. The intrusions began with the discovery of gold near Prescott in 1863. In 1866, the respected Walapai leader, Wauba Yuma, was killed. For the next four years, Walapais engaged the better-armed and better-mounted soldiers in battle. Ultimately, the Walapai surrendered and were moved to the inhospitable lowlands of the Colorado River Indian Reservation. Finding conditions there intolerable, they fled back to their customary territory where, in their brief absence, ranchers and miners had appropriated the habitable areas and taken over many of the springs. Conditions did not improve markedly with the establishment of the reservation in 1883, for heavy grazing had already depleted the Walapai range, wiping out several of the food plants upon which the Indians depended. Impoverished and threatened by epidemic diseases, Walapais sought work in the towns on the Santa Fe Railroad and in the mines. Many, too, turned briefly to the millenarian Ghost Dance in the late 1880s, hoping, to no avail, that the magical power of the dance would expel Anglos from the territory.
Aboriginally, the Upland Pai (Walapai and Havasupai) were culturally and linguistically similar to the Yavapai along their southern boundary and to the Colorado River Yumans to the west. Yet these similarities did not lead to a shared sense of identity. Although Walapais intermarried with the Halchidhoma along the river, raiding and warfare characterized their relationships with the powerful Mohaves and the mobile Yavapais. Enmity intensified with the arrival of Anglo miners and settlers, as Indians were recruited to fight their traditional foes. This process led, in postcontact times, to an increased sense of unity within the beleaguered Walapai bands.