When subjects are confronted with new stimuli that they have to learn to categorize, they have to segment them into relevant features for categorization. Two experiments with four to eleven year old children investigated whether certain irrelevant perceptual aspects of the stimuli prevent learning the relevant features for categorization. In the first experiment, it was shown that children used salient holistic aspects of stimuli for categorization despite the fact that they were only partially relevant for categorization, whereas perfect cues for categorization requiring analysis were not discovered by children. In the second experiment, it was shown that children cannot abstract the relevant cues for categorization when irrelevant perceptual characteristics were crossed with the relevant ones. When these irrelevant cues were absent, children could learn the relevant cues for categorization. Children’s biases towards locally salient properties can impair, or even prevent learning new categories, when these are defined by comparatively less salient features. Results are discussed in terms of the relation between children’s cognitive competences and the abstraction of relevant descriptors for new stimuli.