The forests of Crete were renowned, and were going strong even in Venetian times: Cretan Renaissance literature abounds with pastoral scenes, and tales of deer hunting.
These are the kinds of mountains I grew up seeing in Eastern Crete:
They do have shrubbery. But actual trees are long gone. The first time I saw trees on a mountain was on a visit to Cyprus, and they looked all wrong.
The story I’ve heard is that they were chopped down for firewood, and erosion did the rest. Google Books corroborates:
Many of the forests that were severely exploited recovered and indeed have been through several cycles of exploitation and recovery. For example, deforestation of Crete was a factor in the demise of the Minoan civilization in 1450 BC and yet cypress imported from Crete was used for the construction of the Venetian fleet in the Middle Ages. In the 16th century, the Idhi mountain range in Crete was cpvered in cypress; a century later it was described as a barren spot. The city of Iraklion is located near the site of ancient Knossos, the major city of Minoan Crete. In the 17th century AD, Iraklion repeated the deforestation of the ancient Minoans such that no more local supplies of firewood were available. […] Essentially deforestation all over the Mediterranean occured where populations increased and reforestation occurred where population decreased and people moved out of the area.