Auditory stream segregation allows us to organize our sound environment, by focusing on specific information and ignoring what is unimportant. One previous study reported difficulty in stream segregation ability in children with Asperger syndrome. In order to investigate this question further, we used an interleaved melody recognition task with children in the autism spectrum disorder (ASD). In this task, a probe melody is followed by a mixed sequence, made up of a target melody interleaved with a distractor melody. These two melodies have either the same [0 semitone (ST)] or a different mean frequency (6, 12 or 24 ST separation conditions). Children have to identify if the probe melody is present in the mixed sequence. Children with ASD performed better than typical children when melodies were completely embedded. Conversely, they were impaired in the ST separation conditions. Our results confirm the difficulty of children with ASD in using a frequency cue to organize auditory perceptual information. However, superior performance in the completely embedded condition may result from superior perceptual processes in autism. We propose that this atypical pattern of results might reflect the expression of a single cognitive feature in autism.