Do we have an idea of when the physical capability for vocal language originated? Other great apes have all kinds of vocalizations they can produce, and you don't need THAT many different sounds to support language.
We know from their remains that Neanderthals would have had a rather different range of vocalizations from Homo sapiens, but that doesn't mean they didn't have structured language.