Cochlear implant (CI) recipients have generally good performance for speech in quiet, but have difficulty in adverse conditions such as noise, and more complex tasks such as music listening. Auditory training has been proposed as a means of improving speech perception for CI recipients, and most recent efforts have been focussed on the potential benefits that music-based training may have. This study evaluated two melodic contour training programs that varied in musical mechanism, and evaluated their relative efficacy as measured on speech perception tasks. These melodic contours were simple 5-note sequences formed into 9 patterns such as “Rising” or “Falling”. One training program controlled difficulty by manipulating interval sizes, the other by note durations. Sixteen CI recipients and twelve normal hearing listeners were tested on a speech perception battery for a baseline measure, and then commenced melodic contour training for 6 weeks, after which they were retested. Results indicated there were some benefits for speech perception tasks after melodic contour training. Specifically, consonant perception in quiet was improved, as was question/statement prosody. There was no significant difference between either musical mechanism, suggesting that both conferred benefits for training CI recipients to better perceive speech.