Current knowledge about Paleolithic human plant use is limited by the rare survival of identifiable plant remains as well as the availability of methods for plant detection and identification. By analyzing DNA preserved in cave sediments, we can identify organisms in the absence of any visible remains, opening up new ways to study details of past human behavior, including plant use. Aghitu-3 Cave contains a 15,000-yearlong record (from ∼39,000 to 24,000 cal BP) of Upper Paleolithic human settlement and environmental variability in the Armenian Highlands. Finds from this cave include stone artifacts, faunal remains, bone tools, shell beads, charcoal, and pollen, among others. We applied sedimentary ancient DNA (sedaDNA) metabarcoding to the Aghitu-3 sedimentary sequence and combined this with pollen data to obtain a temporal reconstruction of plant assemblages. Our results reveal a stratification of plant abundance and diversity where sedaDNA reflects periods of human occupation, showing higher diversity in layers with increased human activity. Low pollen concentrations combined with high sedaDNA abundance indicate plant remains may have been brought into the cave by animals or humans during the deposition of the lower two archaeological horizons. Most of the recovered plants are reported to be useful for food, flavor, medicine, and/or technical purposes, demonstrating the potential of the environment around Aghitu-3 Cave to support humans during the Upper Paleolithic. Moreover, we identified several specific plant taxa that strengthen previous findings about Upper Paleolithic plant use in this region (i.e., for medicine and the manufacturing and dyeing of textiles). This study represents the first application of plant sedaDNA analysis of cave sediments for the investigation of potential plant use by prehistoric humans.