In this study, we propose average environmental efficiency, a consistent and robust environmental efficiency measurement, and use it to evaluate the environmental efficiency of Chinese provinces. With the help of a nonparametric directional distance function approach, we can measure all possible environmental efficiency scores of the province by considering all projection directions to the efficient frontier. Then, the mean value of the environmental efficiency scores of a province in all possible projection directions is defined as the average environmental efficiency. Furthermore, we investigate the influencing factors of regional environmental efficiency via a feasible generalized least squares regression approach. The empirical results show that China’s national environmental efficiency has a high value of 0.803, and only nine provinces have average environmental efficiency greater than the average of the country. This implies that two-thirds of provinces still have much room for improvement. In addition, the east area achieved the best average environmental efficiency over the studied period, followed in order by the west area, central area, and northeast area. Moreover, we find that the energy consumption structure, government intervention, and economic openness negatively influence the regional environmental efficiency, while higher education positively influences this efficiency at the 1% significance level.