China’s construction industry has constantly been confronted with the problems, such as high resource consumption, serious pollution and low energy efficiency. Thus, improving the energy efficiency of the construction industry and reducing its energy consumption can not only promote the sustainable development of the socio-economy and eco-economy, but also enhance the overall development level of the construction industry. In the context, the objectives are to put forward a set of systematic methodologies for measuring the energy efficiency of the regional construction industry and analyzing its change trends. First, the energy efficiency index system of the construction industry and its influencing factors are constructed through the literature review. Second, two research methods (the three-stage Data Envelopment Analysis (DEA) model and the Data Envelopment Analysis-Discriminant Analysis (DEA-DA) model) are applied to analyze the energy efficiency in 30 provinces of China and the change trends from 2003 to 2011. The results indicate that after eliminating the influence of the environment factors and random errors, the energy efficiency values of the construction industry in most of the provinces were improved. The mean of China’s energy efficiency of the construction industry in each year was approximately 0.92. Except Shandong with the lowest values, the mean of the other provinces was over 0.8, which reflected that the energy management and utilization levels in the construction industry were relative mature. However, the energy efficiency in most of provinces fluctuated constantly during these nine years, with the peak in 2004 and a downward trend in the overall efficiency after 2004. From the regional aspect, the energy efficiency of the construction industry in the eastern, central and western regions decreased successively; as the development level of the local economy had less significant effects on the energy efficiency, the gaps among the three regions were not obvious.