It is of great practical significance to explore the regional difference characteristics and driving mechanism of the utilization efficiency of construction land under environmental constraints. The purpose is to guide the efficient utilization of urban construction land, alleviate the contradiction between social and economic development and ecological environment in the process of rapid urbanization, as well as achieve regional coordinated development. Taking environmental pollution as an unexpected output into the evaluation system, we systematically studied the spatiotemporal differentiation characteristics, dynamic trend evolution and driving factors of urban construction land use efficiency in Fujian province from 2006 to 2016. Models adopted in this analysis include the non-expected output SE-SBM model, coefficient of variation, and GML index and gray relational model. The results showed that: (1) During 2006-2016, the utilization efficiency of urban construction land in Fujian fluctuated in a sinusoidal pattern. The input-output efficiency had always been put at the effective frontier from 2012 to 2016. It is easy to find the differences of efficiency values between regions. It can also be found that there exists a non-positive correlation between efficiency and economic development level. (2) The spatial pattern suggests that the efficiency of the eastern coastal region is higher than that of the western inland areas, which forms an obvious cluster effect. Although Zhangzhou city is located in the southeastern coastal area, its efficiency value in 2016 was still in an invalid state without a fundamental change, which further illustrates that the radiation driving role of high-efficiency cities is weak. (3) The TFP of Fujian shows a sinusoidal growth trend, and the overall development trend is good. The agglomeration scale effect caused by technological progress is the main reason for the variance in the growth rate of regional TFP. Technological factor is the key to narrow the gap in the growth rate of regional TFP. (4) Urbanization level, ecological input, government regulation, cultivated land resource endowment, R&D investment in science and technology, as well as the advanced industrial structure are the main driving factors affecting the spatiotemporal differentiation and evolution of urban construction land-use efficiency in Fujian province.