Gender identification of human voices was studied in a juvenile population of cochlear implant (CI) users exposed to naturalistic speech stimuli from 20 male and 20 female speakers using two different voice gender perception tasks. Stimulus output patterns were recorded from each individual CI for each stimulus, and features related to voice fundamental frequency and spectral envelope were extracted from these electrical output signals to evaluate the relationship between implant output and behavioral performance. In spite of the fact that temporal and place cues of similar quality were produced by all CI devices, only about half of the subjects were able to label male and female voices correctly. Participants showed evidence of using available temporal cues, but showed no evidence of using place cues. The implants produced a consistent and novel cue to voice gender that participants did not appear to utilize. A subgroup of participants could discriminate male and female voices when two contrasting voices were presented in succession, but were unable to identify gender when voices were singly presented. It is suggested that the nature of long-term auditory categorical memories needs to be studied in more detail in these individuals.