Young children tend to differ from adults in how they learn new categories. In comparison to adults (who rely on selective attention and tend to form explicit rules), children distribute attention widely, forming similarity-based category representations. But, when attention is explicitly directed toward the rule with top-down feedback, children exhibit rule-based classification--though memory performance still indicates distributed attention. Little is known, however, how bottom-up attentional cueing affects the category representations that children form. In our experiment 4-year-olds learned to classify alien creatures composed of binary features. A single “deterministic” feature perfectly predicted category membership, while other features were probabilistically predictive. We manipulated the saliency of the deterministic feature, making it grow and shrink. This manipulation was remarkably effective at facilitating category learning and rule-based classification, but recognition memory still showed evidence of distributed attention. These results help elucidate the important role of attentional processes in the development of categorization.