Learning a particular categorization leads to corresponding changes in the similarity structure of the categorized stimuli. The purpose of the current study was to examine whether different category structures may lead to greater or less similarity change. We created six category structures and examined changes in similarity as a result of categorization in between-participant conditions. The best-supported hypothesis was that the ease of learning a categorization affects change in similarity, with the most change following learning of difficult category structures. There was also support for the hypothesis that similarity change is more likely to occur when the category boundary was not aligned with the physical dimension of variation. Finally, we discuss some methodological challenges in addressing this important research topic.