Paiute Indians occupied the area around what is now Bryce Canyon starting around 1200 A.D. The Paunsaugunt Plateau was used for seasonal hunting and gathering activities, but there is no evidence of permanent settlements.
The legend of Bryce Canyon was explained to a park naturalist in 1936 by Indian Dick, a Paiute elder who then lived on the Kaibab Reservation:
"Before there were humans, the Legend People, To-when-an-ung-wa, lived in that place. There were many of them. They were of many kinds – birds, animals, lizards and such things, but they looked like people. They were not people. They had power to make themselves look that way. For some reason the Legend People in that place were bad; they did something that was not good, perhaps a fight, perhaps some stole something….the tale is not clear at this point. Because they were bad, Coyote turned them all into rocks. You can see them in that place now all turned into rocks; some standing in rows, some sitting down, some holding onto others. You can see their faces, with paint on them just as they were before they became rocks. The name of that place is Angka-ku-wass-a-wits (red painted faces). This is the story the people tell."
Fremont and Anasazi people occupied the portion of the Colorado Plateau near Bryce Canyon from around 200 A.D. until 1200. The Fremont were more to the north and west, with the Anasazi more to the south and east. There is recently discovered evidence of the mixing of these two cultures on the Kaiparowits Plateau.
Native Americans first occupied the Colorado Plateau 12,000 years ago, but no evidence of their activities has yet been found on the Paunsaugunt Plateau.