Vocal communication definitely appeared much before Homo Sapiens Sapiens, mainly with the form of words/sounds without grammar organization.
Sounds, yes, words no.
Especially with Neanderthals, it was anatomically possible for them to talk like modern humans, and it is possible (opinions diverge) that they used a primitive grammar-organized language to communicate.
The documentary I watched said they didn't -- damn, I wish I had the name of it. One scientist made the argument about the palate bone.
Okay, update, I found this on Wikipedia:
Most specialists credit the Neanderthals with speech abilities not radically different from those of modern Homo sapiens. An indirect line of argument is that their tool-making and hunting tactics would have been difficult to learn or execute without some kind of speech. A recent extraction of DNA from Neanderthal bones indicates that Neanderthals had the same version of the FOXP2 gene as modern humans. This gene, once mistakenly described as the 'grammar gene', plays a role in controlling the orofacial movements which (in modern humans) are involved in speech.
During the 1970s, it was widely believed that the Neanderthals lacked modern speech capacities. It was claimed that they possessed a hyoid bone so high up in the vocal tract as to preclude the possibility of producing certain vowel sounds.
The hyoid bone is present in many mammals. It allows a wide range of tongue, pharyngeal and laryngeal movements by bracing these structures alongside each other in order to produce variation. It is now realised that its lowered position is not unique to Homo sapiens, while its relevance to vocal flexibility may have been overstated: although men have a lower larynx, they do not produce a wider range of sounds than women or two-year-old babies. There is no evidence that the larynx position of the Neanderthals impeded the range of vowel sounds they could produce. The discovery of a modern-looking hyoid bone of a Neanderthal man in the Kebara Cave in Israel led its discoverers to argue that the Neanderthals had a descended larynx, and thus human-like speech capabilities. However, other researchers have claimed that the morphology of the hyoid is not indicative of the larynx's position. It is necessary to take into consideration the skull base, the mandible and the cervical vertebrae and a cranial reference plane.
The morphology of the outer and middle ear of Middle Pleistocene hominins from Atapuerca SH in Spain, believed to be proto-Neanderthal, suggests they had an auditory sensitivity similar to modern humans and very different from chimpanzees. They were probably able to differentiate between many different speech sounds.