We examined whether individual differences in working memory influence the facility with which individuals learn new categories. Participants learned two different types of category structures: "rule-based" and "information-integration." Successful learning of the former category structure is thought to be based on explicit hypothesis testing that relies heavily on working memory. Successful learning of the latter category structure is believed to be driven by procedural learning processes that operate largely outside of conscious control. Consistent with a widespread literature touting the positive benefits of working memory and attentional control, the higher one's working memory, the fewer trials one took to learn rule-based categories. The opposite occurred for information-integration categories--the lower one's working memory, the fewer trials one took to learn this category structure. Thus, the positive relation commonly seen between individual differences in working memory and performance can not only be absent, but reversed. As such, a comprehensive understanding of skill learning--and category learning in particular--requires considering the demands of the tasks being performed and the cognitive abilities of the performer.