Current research has shown that although adult cochlear implant (CI) users generally find music to be less enjoyable following implantation, training may help some recipients to improve their music perception. This study developed and administered a questionnaire (The University of Canterbury Music Listening Questionnaire: UCMLQ), to collect information which could then be used to develop such a music training program (MTP). One hundred adult recipients completed the UCMLQ. Results showed that respondents generally found music to be less enjoyable post-implantation, and thought that music did not sound as they would expect it to sound to a person with normal hearing. However, it was reported that music listening could be enhanced by controlling the listening environment, being selective about the music chosen, and using a contralateral HA. The preferred logistics for a MTP were 30-minute sessions, 2–3 times per week, using a DVD format. The program should focus on improving recipients’ ability to recognize tunes, and encompass a wide range of musical styles. The findings support the development of a MTP for CI users to better enable them to enjoy and appreciate music, and to maximize their potential with current technology.