1,5 millions years ago - Homo florensis
Fossil evidence indicates that the main areas of the brain associated with language (Broca's area and Wernicke's area) may have begun to enlarge as long ago as 1 – 1.5 million years, in Homo erectus. However the most complete fossil erectus (nicknamed Turkana Boy; about 1.5 million years old) appears to have lacked a sufficiently tuned ribcage capable of fine control of speech.
The recently discovered Homo floresiensis' ancestors are assumed to have utilized some kind of seafaring device like a raft to reach the island where Homo floresiensis dwelt, furthermore, it would seem probable that this process of colonization was an intentional one, and due to the complexity of such a task, it is suggested that Homo floresiensis and its ancestor, mid-late Homo erectus, must have possessed some form of language which, albeit primitive, would have been able to convey complex concepts. Analysis of the brain of H. floresiensis suggests intellectual capabilities which were comparable to other humans of that time, that is, also not widely divergent from primitive Homo sapiens.
A hypothesis (sometimes calles the "early hypothesis") is that language in some form appeared at the same time as the genus Homo, whose emergence from Australopithecus around two million years ago coincides with the first evidence of stone tools—the so-called Oldowan technology. In this hypothesis, the increase in brain size from Homo habilis through Homo erectus to the Neanderthals and Homo sapiens was itself the product of language.
Definitely it is proved by archaeological findings that humans have been able to social hunting and to use simple tools for more than 1,5 millions of years. Some specialists suppose that at least a simple form of language is necessary for this abilities.
Further information and links:
"Sprache und Evolution" von Horst M. Müller; de Gruyter-Verlag; Berlin 1990