This article introduces total-factor energy productivity change index (TFEPI) based on the concept of total-factor energy efficiency and the Luenberger productivity index to evaluate the energy productivity change of regions in China with a total-factor framework. Moreover, the TFEPI can be decomposed into change in energy efficiency and shift in the energy use technology. According to the computation results, China’s energy productivity was decreasing by 1.4% per year during 2000–2004. The average total-factor energy efficiency improves about 0.6% per year, while total-factor energy technical change declines progressively 2% annually. The factors affecting TFEPI are also examined: (1) The east area has a higher TFEPI than the central and west area; (2) increasing the development status and electricity share of energy consumption will improve the region’s TFEPI performance, while increasing the proportion of GDP generated by the secondary industry deteriorates TFEPI of a region.