The Paine Run Rockshelter (44-AU-158) is an archaeological site in Shenandoah National Park, in Augusta County, Virginia, United States.

The site was discovered during the early 1970s as part of a comprehensive survey of the national park. It is one of fifteen sites that the survey found along Paine Run, a group that also includes archaeological site 44-AU-154 and the Blackrock Springs Site. Located in a mountainside hollow, near three other rockshelters, the site is deeply stratified. It is a small shelter, only about 45 square metres (480 sq ft) in area, and little taller than the average man. The shelter faces northward, toward the narrow floodplain and Paine Run, which flows approximately 15 metres (49 ft) away; it sits just east of site 44-AU-154.

While other archaeological sites in Paine Run Hollow date primarily from the Archaic period, the rockshelter appears to have been occupied at a period of culture change, as the inhabitants were in the process of transitioning from the use of quartzite to cryptocrystalline for their stone tools. Evidence of occupation persists as late as the fourteenth century AD. The site's two components yielded eight hundred and fifteen hundred separate artifacts in total; its artifactual density was the highest of any site recorded by the survey, prompting its interpretation as a regional base camp used frequently by larger groups of people. The surveyors readily conducted a test excavation after finding many lithic flakes, pieces of pottery, and projectile points on the surface. The ceramics are dominated by a form known as "Albemarle cord-marked", which represents nearly two-thirds of potsherds found in the shelter. Meanwhile, the shapes of the surviving lithic flakes (small pieces with almost no cores) appears to indicate that toolmaking done in the shelter consisted of refining rough work that had been performed elsewhere.

The site's archaeological value is so significant that it was listed on the National Register of Historic Places in December 1985, together with 44-AU-154 and the Blackrock Springs Site.