Previous research has disagreed about whether a difficult cognitive skill is best learned by beginning with easy or difficult examples. Two experiments that clarify this debate are reported. Participants in both experiments received one of three types of training on a difficult perceptual categorization task. In one condition, participants began with easy examples, then moved to examples of intermediate difficulty, and finished with the most difficult examples. In a second condition, this order was reversed, and in a third condition, participants saw examples in a random order. The results depended on the type of categories that participants were learning. When the categories could be learned via explicit reasoning (a rule-based task), the three training procedures were equally effective. However, when the categorization rule was difficult to describe verbally (an information-integration task), participants who began with the most difficult items performed much better than participants in the other two conditions.