Consonant musical intervals tend to be more readily processed than dissonant intervals. In the present study, we explore the neural basis for this difference by registering how the brain responds after changes in consonance and dissonance, and how formal musical training modulates these responses. Event-related brain potentials (ERPs) were registered while participants were presented with sequences of consonant intervals interrupted by a dissonant interval, or sequences of dissonant intervals interrupted by a consonant interval. Participants were musicians and non-musicians. Our results show that brain responses triggered by changes in a consonant context differ from those triggered in a dissonant context. Changes in a sequence of consonant intervals are rapidly processed independently of musical expertise, as revealed by a change-related mismatch negativity (MMN, a component of the ERPs triggered by an odd stimulus in a sequence of stimuli) elicited in both musicians and non-musicians. In contrast, changes in a sequence of dissonant intervals elicited a late MMN only in participants with prolonged musical training. These different neural responses might form the basis for the processing advantages observed for consonance over dissonance and provide information about how formal musical training modulates them.