In three experiments, we investigated whether the amount of category overlap constrains the decision strategies used in category learning, and whether such constraints depend on the type of category structures used. Experiments 1 and 2 used a category-learning task requiring perceptual integration of information from multiple dimensions (an information-integration task) and Experiment 3 used a task requiring the application of an explicit strategy (a rule-based task). In the information-integration task, participants used perceptual-integration strategies at moderate levels of category overlap, but explicit strategies at extreme levels of overlap--even when such strategies were suboptimal. In contrast, in the rule-based task, participants used explicit strategies, regardless of the level of category overlap. These data are consistent with a multiple systems view of category learning, and suggest that categorization strategy depends on the type of task that is used, and on the degree to which each stimulus is probabilistically associated with the contrasting categories.