Humans learn categorization rules that are aligned with separable dimensions through a rule-based learning system, which makes learning faster and easier to generalize than categorization rules that require integration of information from different dimensions. Recent research suggests that learning to categorize objects along a completely novel dimension changes its perceptual representation, making it more separable and discriminable. Here, we asked whether such newly learned dimensions could support rule-based category learning. One group received extensive categorization training and a second group did not receive such training. Later, both groups were trained in a task that made use of the category-relevant dimension, and then tested in an analogical transfer task (Experiment 1) and a button–switch interference task (Experiment 2). We expected that only the group with extensive pre-training (with well-learned dimensional representations) would show evidence of rule-based behavior in these tasks. Surprisingly, both groups performed as expected from rule-based learning. A third experiment tested whether a single session (less than 1 h) of training in a categorization task would facilitate learning in a task requiring executive function. There was a substantial learning advantage for a group with brief pre-training with the relevant dimension. We hypothesize that extensive experience with separable dimensions is not required for rule-based category learning; rather, the rule-based system may learn representations “on the fly” that allow rule application. We discuss what kind of neurocomputational model might explain these data best.