Previous studies have demonstrated that cochlear implant (CI) patients are more efficient at performing sound categorisation than sound identification. However, it remains unclear how this categorisation capacity develops with time during the rehabilitation period after implantation. To investigate the role of the post-implantation auditory experience in the broad sound categorisation in CI patients, we recruited CI patients with different durations of CI experience: Newly implanted CI patients (less than six months), Intermediate CI patients (6–14 months) and Experienced CI patients with a duration of implantation greater than 14 months. The patients completed a Free Sorting Task (FST), which allowed them to categorise 16 natural sounds based on their own criteria. We found an early deficit in categorisation, especially for vocal sounds; the categorisation started to improve after approximately six months post-implantation with a change of categorisation strategy which relied on different acoustic cues as a function of time after CI. The separation of the category of vocal sounds from other sounds significantly increased between the Newly implanted and Intermediate groups, i.e. as experience with the cochlear implant was acquired. The categorisation accuracy of vocal sounds was significantly correlated with the post-implantation period only in the group of newly implanted CI patients. This is the first study to show that the categorisation of vocal sounds with respect to non-vocal sounds improves during the rehabilitation period post-implantation. The first six-month post-implantation period appears to be crucial in this process. Our results demonstrate that patients in different rehabilitation periods use different acoustic cues, which increase their complexity with the CI experience.