Learners exposed to an artificial language recognize its abstract structural regularities when instantiated in a novel vocabulary (e.g., Gomez, Gerken, & Schvaneveldt, 2000; Tunney & Altmann, 2001). We asked whether such sensitivity accelerates subsequent learning, and enables acquisition of more complex structure. In Experiment 1, pre-exposure to a category-induction language of the form aX bY sped subsequent learning when the language is instantiated in a different vocabulary. In Experiment 2, while naive learners did not acquire an acX bcY language, in which aX and bY co-occurrence regularities were separated by a c-element, prior experience with an aX bY language provided some benefit. In Experiment 3 we replicated this finding with a 24-hour delay between learning phases, and controlled for prior experience with the aX bY language's prosodic and phonological characteristics. These findings suggest that learners, and the structure they can acquire, change as a function of experience.