The European protected-area network will cease to be efficient for biodiversity conservation, particularly in the Mediterranean region, if species are driven out of protected areas by climate warming. Yet, no empirical evidence of how climate change influences ecological communities in Mediterranean nature reserves really exists. Here, we examine long-term (1998-2011/2012) and short-term (2011-2012) changes in the butterfly fauna of Dadia National Park (Greece) by revisiting 21 and 18 transects in 2011 and 2012 respectively, that were initially surveyed in 1998. We evaluate the temperature trend for the study area for a 22-year-period (1990-2012) in which all three butterfly surveys are included. We also assess changes in community composition and species richness in butterfly communities using information on (a) species' elevational distributions in Greece and (b) Community Temperature Index (calculated from the average temperature of species' geographical ranges in Europe, weighted by species' abundance per transect and year). Despite the protected status of Dadia NP and the subsequent stability of land use regimes, we found a marked change in butterfly community composition over a 13 year period, concomitant with an increase of annual average temperature of 0.95°C. Our analysis gave no evidence of significant year-to-year (2011-2012) variability in butterfly community composition, suggesting that the community composition change we recorded is likely the consequence of long-term environmental change, such as climate warming. We observe an increased abundance of low-elevation species whereas species mainly occurring at higher elevations in the region declined. The Community Temperature Index was found to increase in all habitats except agricultural areas. If equivalent changes occur in other protected areas and taxonomic groups across Mediterranean Europe, new conservation options and approaches for increasing species' resilience may have to be devised.