Foreign-accented speech is generally harder to understand than native-accented speech. This difficulty is reduced for non-native listeners who share their first language with the non-native speaker. It is currently unclear, however, how non-native listeners deal with foreign-accented speech produced by speakers of a different language. We show that the process of (second) language acquisition is associated with an increase in the relative difficulty of processing foreign-accented speech. Therefore, experiencing greater relative difficulty with foreign-accented speech compared with native speech is a marker of language proficiency. These results contribute to our understanding of how phonological categories are acquired during second language learning.