Between about 10,000 and 6,000 BCE, great parts of what is now called the Sahara were not a desert, but looked more like a savanna. There were perennial lakes and there was sufficient vegetation to make sure that big, wild animals could feed themselves. On some places, you can still find the petrified remains of the ancient trees.
There were also human beings living on the savanna, who made rock art, which is distinguished from later rock art because of the use of deep relief, which was created with tools made of flint stone. It is called the "Wild Fauna" style, and the Wadi Mathendous is one of the best sites to see these works of prehistoric art. The artists depicted rhinoceroses, crocodiles, hippopotamuses, giraffes, wild asses, felines, and now extinct long-horned buffaloes (buffalus antiquus).
Small hunter, big elephant
One of the surprising aspects of these rock reliefs is the lack of proportion. Sometimes, the animals are shown way too large, while the humans - usually hunters - are too small. This has been taken as indicative of the fear that the wild beasts inspired, but the truth is that we do not know why the prehistoric artists did this.