Traditionally, the transition between Middle and Upper Paleolithic is thought to have been marked at ~45,000 years ago. This transition was known as the "Creative Explosion", when Paleolithic cave paintings, sophisticated hunting techniques, portable art such as Venus figurines, and other cultural traits were thought to have first appeared. But twenty years of research in South Africa, North Africa and the Levant have increased the time depth of this explosion, leading researchers to the inescapable conclusion that the "explosion" started in Africa, perhaps as long ago as 250,000 years ago, culminating in the Upper Paleolithic ca ~45,0000.
Interestingly, there is now more evidence of modern behaviors between 70,000 and 100,000 years ago than there is between 70,000 and 45,000 years ago. It remains to be seen whether this situation is an anomaly based on our admittedly less-than-complete data set of the world's paleoanthropology, or a reflection that modern behavior had an early flourishing, then went dormant for some 25,000 years.
Sources and Further Information
Paleolithic cave paintings
Bouzouggar, A., et al. 2007 82,000-year-old shell beads from North Africa and implications for the origins of modern human behavior. Proceedings of the National Academy of Sciences 104(24):9964-9969.
Vanhaeren, Marian, et al. 2006 Middle Paleolithic Shell Beads in Israel and Algeria. Science 312:1785-1788.