The cross efficiency (CE) model has been accepted as an alternative approach for evaluating carbon emission efficiency in data envelopment analysis (DEA). However, the current studies can't examine the time effect of economic and energy inputs on regional productivity. This paper proposes a novel method combing CE model with Malmquist productivity index (CE-MPI) to discover a dynamic change of carbon emission efficiencies of China's 30 provinces. The results indicate that Eastern Zone is the most advanced in carbon emission efficiency as well as productivity capacity but the efficiency gap between Inter-mediate and Western Zone is less than 5.7 percent point. The technology progress drives the improvement of the CE-MPI. But the efficiency change pulls down the level of productivity for most zones. Based on the efficiency change and the technical change, China's 30 provinces are divided into four classification and given different recommendations for improving carbon emission efficiency.