The brain is constantly generating predictions of future sensory input to enable efficient adaptation. In the auditory domain, this applies also to the processing of speech. Here we aimed to determine whether the brain predicts the following segments of speech input on the basis of language-specific phonological rules that concern non-adjacent phonemes. Auditory event-related potentials (ERP) were recorded in a mismatch negativity (MMN) paradigm, where the Finnish vowel harmony, determined by the first syllables of pseudowords, either constrained or did not constrain the phonological composition of pseudoword endings. The phonological rule of vowel harmony was expected to create predictions about phonologically legal pseudoword endings. Results showed that MMN responses were larger for phonologically illegal than legal pseudowords, and P3a was elicited only for illegal pseudowords. This supports the hypothesis that speech input is evaluated against context-dependent phonological predictions that facilitate speech processing.