Open-cut coal mining can seriously disturb and reshape natural landscapes which results in a range of impacts on local ecosystems and the services they provide. To address the negative impacts of disturbance, progressive rehabilitation is commonly advocated. However, there is little research focusing on how these impacts affect ecosystem services within mine sites and changes over time. The aim of this study was to assess the cumulative impacts of mining disturbance and rehabilitation on ecosystem services through mapping and quantifying changes at multiple spatial and temporal scales. Four ecosystem services including carbon sequestration, air quality regulation, soil conservation and water yield were assessed in 1989, 1997, 2005 and 2013. Disturbance and rehabilitation was mapped using LandTrendr algorithm with Landsat. We mapped spatial patterns and pixel values for each ecosystem service with corresponding model and the landscape changes were analyzed with landscape metrics. In addition, we assessed synergies and trade-offs using Spearman's correlation coefficient for different landscape classes and scales. The results showed that carbon sequestration, air quality regulation and water yield services were both positively and negatively affected by vegetation cover changes due to mined land disturbance and rehabilitation, while soil conservation service were mainly influenced by topographic changes. There were strong interactions between carbon sequestration, air quality regulation and water yield, which were steady among different spatial scales and landscape types. Soil conservation correlations were weak and changed substantially due to differences of spatial scales and landscape types. Although there are limitations associated with data accessibility, this study provides a new research method for mapping impacts of mining on ecosystem services, which offer spatially explicit information for decision-makers and environmental regulators to carry out feasible policies, balancing mining development with ecosystem services provision.