This study aimed to investigate perception and processing of musical features in prelingually deaf adolescent CI-users and examine whether this is influenced by music training. Eleven adolescent CI-users received intensive music training for two weeks. Before and after training they completed a session of behavioral tests and EEG recordings. CI users significantly improved their overall behavioral perception of music and, in particular, their discrimination of melodic contour and rhythm. Though smaller and later compared to normal-hearing controls, CI-users showed significant mismatch negativity responses for timbre, intensity and rhythm but not for pitch. No effect of training was found in the MMN responses. The findings indicate that despite congenital deafness and late implantation, young CI users are able to discriminate details in music. Furthermore, the behavioral advances suggest that, in a wider perspective, music training may serve as a supplementary measure of rehabilitation.