Temperature profoundly influences the physiology and life history characteristics of organisms, particularly in terms of body size. Because so many critical parameters scale with body mass, long-term temperature fluctuations can have dramatic impacts. We examined the response of a small mammalian herbivore, the bushy-tailed woodrat (Neotoma cinerea), to temperature change from 20 000 yr BP to present, at five sites within the Colorado Plateau. Our investigations focused on the relationship between temperature, plant composition and abundance, and woodrat size. Body size was estimated by measuring fossil fecal pellets, a technique validated in earlier work. We found significant and highly covariable patterns in body mass over the five locations, suggesting that responses to temperature fluctuations during the late Quaternary have been very similar. Although woodrat mass and the occurrence of several plant species in the fossil record were significantly correlated, in virtually all instances changes in woodrat size preceded changes in vegetational composition. These results may be due to the greater sensitivity of woodrats to temperature, or to the shorter generation times of woodrats as compared to most plants. An alternative hypothesis is that winter temperatures increased before summer ones. Woodrats are highly sensitive to warmer winters, whereas little response would be expected from forest/woodland plants growing at their lower limits. Our work suggests that woodrat size is a precise paleothermometer, yielding information about temperature variation over relatively short-term temporal and regional scales.