Individuals differ in their ability to perceive and learn unfamiliar speech sounds, but we lack a comprehensive theoretical account that predicts individual differences in this skill. Predominant theories largely attribute difficulties of non-native speech perception to the relationships between non-native speech sounds/contrasts and native-language categories. The goal of the current study was to test whether the predictions made by these theories can be extended to predict individual differences in naive perception of non-native speech sounds or learning of these sounds. Specifically, we hypothesized that the internal structure of native-language speech categories is the cause of difficulty in perception of unfamiliar sounds such that learners who show more graded (i.e., less categorical) perception of sounds in their native language would have an advantage for perceiving non-native speech sounds because they would be less likely to assimilate unfamiliar speech tokens to their native-language categories. We tested this prediction in two experiments in which listeners categorized speech continua in their native language and performed tasks of discrimination or identification of difficult non-native speech sound contrasts. Overall, results did not support the hypothesis that individual differences in categorical perception of native-language speech sounds is responsible for variability in sensitivity to non-native speech sounds. However, participants who responded more consistently on a speech categorization task showed more accurate perception of non-native speech sounds. This suggests that individual differences in non-native speech perception are more related to the stability of phonetic processing abilities than to individual differences in phonetic category structure.