Categorization is essential for survival, and it is a widely studied cognitive adaptation in humans and animals. An influential neuroscience perspective differentiates in humans an explicit, rule-based categorization system from an implicit system that slowly associates response outputs to different regions of perceptual space. This perspective is being extended to study categorization in other vertebrate species, using category tasks that have a one-dimensional, rule-based solution or a two-dimensional, information-integration solution. Humans, macaques, and capuchin monkeys strongly dimensionalize perceptual stimuli and learn rule-based tasks more quickly. In sharp contrast, pigeons learn these two tasks equally quickly. Pigeons represent a cognitive system in which the commitment to dimensional analysis and category rules was not strongly made. Their results may reveal the character of the ancestral vertebrate categorization system from which that of primates emerged. The primate results establish continuity with human cognition, suggesting that nonhuman primates share aspects of humans' capacity for explicit cognition. The emergence of dimensional analysis and rule learning could have been an important step in primates' cognitive evolution.