We examined effects of normal aging on category learning, comparing performance and strategy choice on two learning tasks: one where a one-dimensional rule governed category membership and one where a multidimensional rule defined category structure. Paradoxically, we demonstrated that older adults can outperform younger adults in some types of complex category learning. In the current task - which required that multiple dimensions be integrated - simpler integration rules enabled more rapid achievement of reasonable levels of performance. As cognitive aging is associated with a reduction in working memory resources, older adults tended to adopt these simpler decision rules more often, facilitating complex category leaning. Results provide some unique evidence highlighting potential adaptive benefits of cognitive aging. Implications are discussed.