There are references in the bible to the "un-penetrable forests of Lebanon". That's on the order of 3K years ago.

I would think that the the cause is complex but humans removing trees until they are gone is probably part of the problem.