Há cerca de 20 mil anos, no auge do último máximo glaciar, quase toda a superfície europeia estava debaixo de gelo, provocando migrações de espécies sensíveis para sul. O Sul da Península Ibérica constituiu um refúgio, pois raramente terá estado sob um manto gelado. Nesta região as características de fauna e flora não sofreram grandes alterações. A vegetação e a fauna atuais do Algarve são relativamente semelhantes desde então, pese embora o natural desaparecimento das espécies de animais de grande porte, como o leão e o auroque. Digno de nota por se tratar do maior sítio arqueológico do Paleolítico Superior em Portugal e o mais antigo no sul da península ibérica, o abrigo rochoso de Vale de Boi, no concelho de Vila do Bispo, regista ocupações entre os 32.000 e os 6.000 anos antes do presente, pelo homem moderno, homo sapiens sapiens. Foi escolhido por caçadores-recolectores provavelmente porque, a uma centena de metros, próximo da Boca do Rio, teria existido uma lagoa de ligação ao mar, que alteraria o teor salino da água e que funcionaria como pólo de atração para os animais. Do abrigo, num ponto mais elevado na serra, seria possível visualizar e caçar as presas que ali iam beber. Ocupando 13 mil metros quadrados, a boa preservação orgânica revelou, entre outros factos uma dieta à base de recursos marinhos pouco frequente em sítios deste período. Entre os diversos materiais recolhidos são de realçar as pontas de flecha e uma peça de arte móvel, datada do Solutrense, há cerca de 20 mil anos, com cerca de 20 cm, representando vários auroques sobrepostos.
No concelho de Lagos são ainda de referir os locais do Paleolítico Superior (13.000 anos) situados a norte de Espiche.
