In the category learning literature, similarity models have monopolized a good deal of research. The prototype and exemplar models are both based on the idea that people represent the structure of categories and category instances in the physical world in a mental similarity space. However, evidence for these models comes mainly from paradigms that provide subjects with deterministic feedback (i.e., exemplars belong to their corresponding categories with probability = 1). There is evidence that results obtained with deterministic feedback paradigms may not generalize well under probabilistic feedback conditions (i.e., where exemplars belong to their corresponding categories with probability less than 1). In this current work, we also suggest that probabilistic feedback may better reflect natural conditions, which is another important reason to pursue probabilistic feedback research. Thus, in the current work we set up a category learning experiment with probabilistic feedback and use it to evaluate different models. In addition to the two similarity models discussed above, we also use an associationist model that does not rely on the similarity construct. To compare our three models, we rely on computational modeling, which is a standard way of model comparison in cognitive psychology. Our results show that our associationist model outperforms similarity models on all our model evaluation measures. After presenting our results, we discuss why the similarity-based models fail, and also suggest some future lines of research that are possible using probabilistic feedback procedures.