Fire regime changes are considered a major threat to future biodiversity in the Mediterranean Basin. Such predictions remain uncertain, given that fire regime changes and their ecological impacts occur over timescales that are too long for direct observation. Here we analyse centennial- and millennial-scale shifts in fire regimes and compositional turnover to track the consequences of fire regime shifts on Mediterranean vegetation diversity. We estimated rate-of-change, richness and compositional turnover (beta diversity) in 13 selected high-resolution palaeoecological records from Mediterranean Iberia and compared these with charcoal-inferred fire regime changes. Event sequence analysis showed fire regime shifts to be significantly temporally associated with compositional turnover, particularly during the last three millennia. We find that the timing and direction of fire and diversity change in Mediterranean Iberia are best explained by long-term human–environment interactions dating back perhaps 7500 years. Evidence suggests that Neolithic burning propagated a first wave of increasing vegetation openness and promoted woodland diversity around early farming settlements. Landscape transformation intensified around 5500 to 5000 cal. yr BP and accelerated during the last two millennia, as fire led to permanent transitions in ecosystem state. These fire episodes increased open vegetation diversity, decreased woodland diversity and significantly altered richness on a regional scale. Our study suggests that anthropogenic fires played a primary role in diversity changes in Mediterranean Iberia. Their millennia-long legacy in today’s vegetation should be considered for biodiversity conservation and landscape management.