Phonotactics--constraints on the position and combination of speech sounds within syllables--are subject to statistical differences that gradiently affect speaker and listener behavior (e.g., Vitevitch & Luce, 1999). What statistical properties drive the acquisition of such constraints? Because they are naturally highly correlated, previous work has been unable to dissociate the contribution of 2 properties: contextual variability (the number of unique phonological contexts in which a phonotactic pattern appears) and exemplar strength (the overall number of times the pattern appears). Using an artificial language learning paradigm, 3 experiments disentangled the effects of variability and strength, indexed by type and token frequency, respectively, on the learning of gradient phonotactics. When the 2 factors were decorrelated (Experiment 2), participants showed greater generalization of patterns advantaged for contextual variability, but not those advantaged for exemplar strength. When the 2 factors were anticorrelated (Experiment 3), participants preferred patterns advantaged in contextual variability, even though they were disadvantaged for exemplar strength. These results suggest that contextual variability is the key force driving phonotactic learning, as it allows learners to home in on the invariant features of the input.