An explicit, rule-based, category-learning task with abstract visual stimuli was administered to 50 healthy older adults and 48 younger adults. Accuracy and reaction time (RT) were examined for the effects of age, perceptual abilities, rule memory, rule complexity, stimulus novelty, and response competition. Older adults performed at equivalent levels to younger adults when applying a simple rule, but showed performance decrements when applying a more complex rule. The age effect interacted with both stimulus novelty and response competition, and was not eliminated after controlling for basic perceptual abilities and rule memory. The authors suggest that older adults show category learning deficits in conditions that require enhanced cognitive control. These results are discussed in reference to the growing body of literature regarding age-related change in executive abilities and frontal lobe function.