Archaeological finds in Iran show that women and men applied makeup and arrayed themselves with ornaments approximately 10,000 years ago, a trend which began from religious convictions rather than mere beautification motivations.
Archaeologists have discovered various instruments of make-up and ornamental items in the Burnt City, which date back to the third millennium BCE.
The caves of the Bakhtiari region, where the first hunter-gatherers settled at the end of the ice age, have yielded not only stone tools, daggers and grindstones but also several stones covered with red ocher.
Seems mostly circumstantial, but then again I think most people more or less assume that people have been painting themselves for a looooong time.