In contrast to the static categories assumed in most categorization experiments, many real world categories undergo gradual and systematic change in their definitions over time. Four experiments were carried out to study such category change. In these studies, subjects successfully adjust as category change occurs, but also show a lingering and cumulative effect of past observations. The subjects' performance can be closely modeled by incorporating memory decay for past observations into Anderson's (1990, 1991) rational categorization algorithm or into a version of Nosofsky's (1986) exemplar categorization model. The resulting models suggest that the decay function is closer to a power law than to an exponential, and that decay occurs both by item and by time, with the item decay being stronger than the time decay. The finding of power law decay gives additional support to claims that exemplar memories are used in categorization.