Counterfactual explanations are a well-known technique in Explainable Machine Learning (XML) to provide simple explanations on complex Machine Learning (ML) models. Through understandable “what if” scenarios, counterfactuals explore how changes in the input data affect the results of a model. This article leverages counterfactual explanations for sustainable tourism, an emerging approach within the tourism industry to mitigate the negative impacts of mass tourism on ecological systems and local communities. The proposed method analyzes the relationships between several Sustainable Tourism Indicators (STIs) defined for a specific tourist destination and its general sustainability assessment. It identifies the key changes needed in the STIs to achieve an improved global sustainability score. As a result, a decision-making system is offered for sustainable tourism management, which domain experts can use to make more informed decisions. The effectiveness of the proposed method is illustrated through its application to Mallorca, a popular Spanish tourist destination.