There is considerable debate about whether the early processing of sounds depends on whether they form part of speech. Proponents of such speech specificity postulate the existence of language-dependent memory traces, which are activated in the processing of speech but not when equally complex, acoustic non-speech stimuli are processed. Here we report the existence of these traces in the human brain. We presented to Finnish subjects the Finnish phoneme prototype /e/ as the frequent stimulus, and other Finnish phoneme prototypes or a non-prototype (the Estonian prototype /õ/) as the infrequent stimulus. We found that the brain's automatic change-detection response, reflected electrically as the mismatch negativity (MMN), was enhanced when the infrequent, deviant stimulus was a prototype (the Finnish /ö/) relative to when it was a non-prototype (the Estonian /õ/). These phonemic traces, revealed by MMN, are language-specific, as /õ/ caused enhancement of MMN in Estonians. Whole-head magnetic recordings located the source of this native-language, phoneme-related response enhancement, and thus the language-specific memory traces, in the auditory cortex of the left hemisphere.