This article examines relational category learning in light of 2 influential theories of concept acquisition: the structure-mapping theory of analogy and theories of feature-based category learning. According to current theories of analogy, comparing 2 instances of a relational concept enables alignment of their elements and reveals their shared relational structure. Therefore, learning relationally defined categories should be faster when comparing items of the same category than when comparing items of different categories. By contrast, feature-based theories predict a benefit of between-category comparisons, because such comparisons direct attention to the features that discriminate the categories. The present experiments tested these predictions using a 2-category classification-learning task in which 2 items are presented on every trial: either in the same category (match condition) or in different categories (contrast condition). Subjects in the contrast condition outperformed those in the match condition for feature-based categories (Experiment 1) and across 4 different types of relational categories (Experiments 1–4). Although theorists have posited that structure-mapping theory is directly applicable to relational category learning, the present findings pose a distinct challenge to this assertion. We propose that many relational categories are learnable based solely on which relations are present in the stimulus rather than requiring explicitly compositional representations based on role-filler binding. This process would be akin to feature processing and would not require structural alignment. This theoretical proposal, together with the empirical results, may lead to a better understanding of when people do and do not engage in the cognitively demanding process of structural alignment.