Racial categorization is a widespread phenomenon at the root of many of the most pressing problems in modern human life. These facts are peculiar from an evolutionary perspective given that racial categories as we understand them today are not biologically real and are evolutionarily novel inventions. The alliance hypothesis of race attempts to reconcile these facts by proposing that modern racial categorization is a byproduct of a system designed for ancestral alliance detection. Support for this hypothesis comes from studies demonstrating that redirecting coalitional psychology can suppress racial categorization. However, the capacity of coalitional psychology to generate racial categories from scratch is less clear. Here we use a series of agent-based models to provide a sufficiency test of the alliance hypothesis. We generate populations of agents that vary on arbitrary phenotypic dimensions and engage in cooperative interactions with one another. We show that the introduction of a coalitional psychology that attempts to detect patterns of allegiance based on available cues can hallucinate and then reify correlations between phenotype and allegiance, leading to the emergence of social groups that vary systematically by phenotype. This occurs even when phenotype is in reality distributed continuously and has no true connection to behavior. Furthermore, consistent with psychological evidence, such phenotypic classification is suppressed when valid cues of allegiance are made available. These models provide evidence that a coalitional psychology alone can be sufficient to create beliefs in phenotype-based social categories even when no such categories truly exist.