There are lots of genetic and cultural foundations to language that likely developed in spurts over time. Yet some final genetic piece seems to have been a tipping point that sent communication from primitive to complex very rapidly. In the first place, any improvement in communication between tribesmen conferred such an advantage in exploiting an environment that each of them must have spread rapidly. That some last piece also did so may seem odd to those accustomed to the evolutionary narrative of slow, almost imperceptible improvement, but it is likely anyway.
The evidence for this is not archaeological but from events occurring in our lifetimes. A simplified, stripped-down, invented language becomes complex as soon as a generation of children grows up with it. A pidgin language is such a stripped-down item, invented by adults who come in contact with each other for trade. "Pidgin" may in fact be a corruption of "business," as the language Tok Pissin was originally a "talk business" language. But when infants come into the picture, learning the language from birth, it develops word-order, declensions, and subtler distinctions within a generation. It becomes what we call a creole. A creole is a real, complex language, as subtle as the other 6000 languages in the world. It sounds primitive to the speakers of the original language because the new speakers seem to just plain have it wrong, and use mispronunciations and simplifications as foundation pieces. Yet it has its own internal subtleties.
All this happens in a generation. The kids just do it. No one tells them they're supposed to make up a sophisticated language, but they make what they need, and their communication needs are complex. They have a full genetic pre-loading to make a language if the building blocks are placed in their hearing. There is even a Nicaraguan school for the deaf where the children spontaneously made up an enormously complex sign language based on the few signs adults brought to them. No one told them to. When men invade and take local wives who speak a different language, the children of that village will develop what they need.
As I noted, for this puzzle piece to have a dramatic effect it had to have been undergirded by a host of other cognitive abilities, each of which developed in their own time. The FOXP2 gene (pronounced forkhead box 2 not "fox") is often nominated as that last puzzle piece for language. While the story is fascinating and something similar may indeed be the key, FOXP2 doesn't yet have the explanatory power to sustain its popular reputation. Still, it is a good illustration of the concept of "final genetic piece" language.
The first fully complex languages around 60-80,000 years ago may not have been as fully sophisticated as current human languages. There have been cognitive improvements in humans since then, two of which have been identified at 37,000 and 6,000 years ago. Don't jump to Edenic conclusions on that last improvement, though. But the improvements were so dramatic that these speaking peoples outcompeted and displaced everyone else quickly. We are all descended from them.
We are also watching an example of this dramatic drive to language complexity - also driven by the young - happening under our view. Internet communication is developing complexity to keep pace with its needs. For content-heavy communication we still use standard English. But for electronic social communication the needs are different. Words are stripped down to initials (ROTFL, FTW) which seems an uber-efficiency to communicate phrases and sentences. Yet these phrases and sentences are often only social signs, light on content but meant to express mood. Emoticons and punctuation repeats serve a similar function. One can view them as highly efficient ways of communicating nuance with a few strokes. But one can look through the other end of the telescope and see them as mostly content-useless, formulaic conventions. Both are true. Kids are both simplifying and complicating the language at the same time to meet the specific needs of electronic social networking.
No one told them to. They just do it. Same as thousands of years ago. Once a few children had been born with the necessary genetic pieces in place (and so likely siblings or cousins) they would have made a language. The other children in the tribe would have had the smarts to imitate a lot of it, even if they didn't get it all, and this would create an even larger pool of speakers. When those children grew to adulthood, that tribe would kick butt.