Arid regions are especially vulnerable to climate change and land use. More than one-third of Earth's population relies on these ecosystems. Modern observations lack the temporal depth to determine vegetation responses to climate and human activity, but paleoecological and archaeological records can be used to investigate these relationships. Decreasing rainfall across the Late Holocene provides a case study for vegetation response to changing hydroclimate. Rock hyrax (Procavia capensis) middens preserve paleoenvironmental indicators in arid environments where traditional archives are unavailable. Pollen from modern middens collected in Dhofar, Oman, demonstrates the reliability of this archive. Pollen, stable isotope (delta C-13, delta N-15), and microcharcoal data from fossil middens reveal changes in vegetation, relative moisture, and fire from 4000 cal yr BP to the present. Trees limited to moister areas (e.g., Terminalia) today existed farther inland at similar to 3100 cal yr BP. After similar to 2900 cal yr BP, taxa with more xeric affiliations (e.g., Senegalia) had increased. Coprophilous fungal spores (Sporormiella) and grazing indicator pollen revealed an amplified signal of domesticate grazing at similar to 1000 cal yr BP. This indicates that trees associated with semiarid environments were maintained in the interior desert during similar to 3000-4000 yr of decreasing rainfall and that impacts of human activity intensified after the transition to a drier environment.