Local governments and coal enterprises are recognized as important subjects of liability in implementation of the ecological restoration of mine deposit systems. From the perspective of evolutionary game theory, this study has explored the evolution of local government and coal enterprises' decision-making in implementation, constructed evolutionary game models, discovered the participants' behavior evolution law and evolutionary, stable strategies based on a replicator dynamics equation, and analyzed the factors that influence the choice of implementation strategies. The Longkou mining area in Shandong Province was selected as an empirical research object. The results show that the governmental supervision changes with the enterprises' ecological restoration degree,which is originally low. As the supervision is strengthened and ecological restoration improves, the local government may advisably loosen control to a certain extent, which ensures that the mechanism will evolve toward the optimal state. This is assumed to lead the local government and coal enterprises to jointly promote the ecological restoration by means of dynamically adjusting the amount of deposit, increasing tax incentives, reducing the restoration costs for coal enterprises, and strengthening the local government's environmental performance assessment.