Civilization probably evolved gradually over tens of thousands of years even before the advent of writing. The matching of speech to written symbols would seem to be the culmination of millennia of developing forms of communication which in turn formed the basis of what we know of as civilization. As speech, tool use, and painting were added over the generations to the cultural repertoires of our prehistoric ancestors, the nucleus of our ability to form civilizations must have grown dramatically. As the Usenet newsgroup talk.origins explains in its entry "Hominid Species," the first hominid species was Ardipithecus ramidus, which lived about 5.8-4.4 million years ago. It was something like a chimpanzee and appears to have lived in forests. This was the first creature in the line that descended into human beings, and after several intermediates came:
  • Homo habilis (2.4-1.5 million years ago)
  • Homo erectus (1.8 million and 300,000 years ago)
  • Homo antecessor (at least 780,000 years ago)
  • Homo sapiens (archaic) (also Homo heidelbergensis) (about 500,000 years ago)
  • Homo sapiens neanderthalensis (200,000-300,000 years ago), whose description includes these lines: "A large number of tools and weapons have been found, more advanced than those of Homo erectus. Neandertals were formidable hunters, and are the first people known to have buried their dead, with the oldest known burial site being about 100,000 years old." Although far predating the first evidence of writing, these seem to be clear indicators of civilizational activity.
  • Homo sapiens sapiens (modern) -- our line -- began about 120,000 years ago, but even by the Cro-Magnon era 40,000 years ago, humans were creating elaborate cave paintings.
It may well be that civilization in its broadest sense began with the earliest human speech and painting at least 40,000 years ago.

Cletus the Foetus has raised the salient point of establishing the difference between a culture and a civilization, and whether a culture must be sedentary before it can be considered a civilization. I think of it this way: imagine a graph extending from the first hominid groups to modern day nation-states. To keep things simple, one could have two variables plotted on this graph: (1) the degree to which a culture is geographically stationary and (2) the sophistication of their writing/written record system. Merriam-Webster's Collegiate Dictionary gives these definitions for culture and civilization (I have chosen what I think are the most relevant senses):

civilization
1 a : a relatively high level of cultural and technological development; specifically : the stage of cultural development at which writing and the keeping of written records is attained
culture
5 a : the integrated pattern of human knowledge, belief, and behavior that depends upon man's capacity for learning and transmitting knowledge to succeeding generations b : the customary beliefs, social forms, and material traits of a racial, religious, or social group

If we were to take writing alone as the prime criterion of civilization, then certainly our earliest written alphabets would establish the start of civilization at about 7,000 years ago. But then there is the less specific term "written records," which could certainly include items such as carvings and paintings. It seems that hominids developed more quickly along the axis of "sedentaryness" than they did along the axis of written records. Yet over time it is easy to envision that the two things--being stationary and keeping written records--began to accelerate in sophistication.

Because of the often subtle gradations between one level of civilized activity and the next, one can see how burying the dead could have evolved from (a) burying and moving on to (b) burying and living near the burial site. To the extent that certain geographic areas permitted such prolonged habitation, sedentary cultures could thrive in them. The invention of agriculture marks where that progress spiked upward, but it is easy to see that cultures could have been sedentary for extended periods of time through the good graces of friendly lands.

Similarly, with written records, which hominids have long used to "learn and transmit knowledge to succeeding generations," one can see cave paintings as an early form of written records, and who knows what other things were written down on perishable surfaces such as dirt or wooden sticks.

We would normally consider these graphs to show that both elements (increasingly stationary and increasingly sophisticated with writing) would tend to increase in lockstep, but perhaps they do not. There have been nomadic civilizations, and there have been stationary cultures who relied a lot on speech instead of writing. Even now, one could argue that many people are technically living in sedentary civilizations but they travel three weeks per month, so they exist in a sort of hybrid state.

If we could unearth from the past the earliest ways in which hominids dealt with each other, perhaps we could find some clues to solving apparently intractable problems such as war, terrorism, and conflicts among religions.