In several places, near both the eastern and western boundaries of the park, remains of prehistoric peoples have been found buried, mostly fragments of stone tools and weapons, with some pieces of pottery.
In the neolithic age, around 5,000 years ago, South Pacific islanders began moving to Taiwan. They were the ancestors of the Pingpu or plains aboriginal tribes, and of the Kaoshan or mountain aboriginal tribes of today. The mountain tribes include many distinct groups, with different languages and culture, all of Malayo-Polynesian type. Of the mountain tribes the Atayal and Saisiyat tribes probably came to Taiwan the earliest; they settled in northern and central Taiwan. They never lived up in the high mountains, but made their homes lower down: the Atayal at altitudes of 1,000-1,500 meters, the Saisiyat at 500-1,000 meters. They lived by hunting, fishing and farming. It is calculated that today there are some 18,000 Atayal and Saisiyat people living around the outside of Shei-Pa National Park. Though there are no settlements inside the park boundary, the aborigines have long been active in the high mountain areas, and have left their mark on the history of the park: e.g. many of the mountain trails have been traced back to trails the Atayal made for hunting or social contacts, and many places still have the old Atayal names, for instance Kailantekun Mountain and Mutelebu Mountain along the Shengling Trail, and Kalahei Mountain, one of the "Wuling Quadruple Mountains."