The Algarve is a mature destination in the south of Portugal and is mainly well-known for its offerings of sun and sea. In addition to strong seasonal changes, the region also faces strong competition from other nearby destinations, which has affected its ability to better attract tourists. Regional stakeholders have recognized the need to diversify the tourist experience, and a strong effort has been dedicated to the development of complementary tourist products, with special attention to eco-tourism. The present study uses data from a survey of tourists who visited the Algarve in December 2010 (low season) to determine the extent to which tourists visiting the region would actively search for nature-related activities, and the profile of these individuals. In particular, the study aims to understand whether these tourists share environmentally friendly values or, instead, have chosen the Algarve based on its attributes of traditional appealing climatic conditions and beaches. Depending on whether nature-based tourism in the Algarve is a fact or a myth, strategies for repositioning the destination can be adapted, new tourist products can be proposed and communication campaigns may need to be rethought.