Research in speech and music shows that listeners model their auditory environment to form expectations about future input. Here we asked how the ability to predict upcoming musical tones based on both general implicit knowledge of musical structure and familiarity with a particular tune influence early portions of the auditory evoked response (AER). Using electroencephalography, we examined how predictability influenced brain responses to repeated tunes. The musical stimuli were simple, monophonic Irish folk tunes (Normal) and Random sequences in which the notes of each tune were presented in randomized order. Because the Random stimuli lacked musical structure, we hypothesized that listeners would be unsuccessful in learning or creating predictive models for these sequences. Differences were observed in early AER between the Normal and Random sequences. The results suggest that listeners successfully learn, remember and model the Normal sequences, but are unable to do this for Random sequences.