The pubic louse evolved around 3.3 million years ago, … and it could not have done so until ancestral humans lost their body fur, creating its niche. What’s more, [we have] dated the evolution of body lice, which live in clothing, to around 70,000 years ago. So it looks like our ancestors wandered around stark naked for a very long time. (more)

Theories of why we stayed naked for so long vary:

When our ancestors moved to more open ground, natural selection would have favoured individuals with very fine hair to help cooling air circulate around their sweaty bodies. But sweating requires a large fluid intake, which means living near rivers or steams, whose banks tend to be wooded and shady – thus reducing the need to sweat. What’s more, the Pleistocene ice age set in around 1.6 million years ago and even in Africa the nights would have been chilly. … Other animals on the savannah have hung on to their fur. …

[Some argue] that we did not shed our pelts until we were smart enough to deal with the consequences, which was probably after modern humans evolved, about 200,000 years ago. “We can make things to compensate for fur loss such as clothing, shelter and fire.” … [Some argue] natural selection favoured less hairy individuals because fur harbours parasites that spread disease. Later, sexual selection lent a hand, as people with clear, unblemished skin advertising their good health became the most desirable sexual partners and passed on more genes.