Environmental decentralization is an institutional factor that influences the effect of ecological environment governance. Based on panel data of provinces in China from 2008 to 2015, this paper evaluates the indicators of environmental decentralization, and uses a fixed-effect model and a threshold model to test the influence of environmental decentralization and environmental regulation on environmental pollution. The results indicate that China’s environmental decentralization can significantly curb environmental pollution in general. There is a U-shaped relationship between environmental decentralization and environmental pollution. Reasonable environmental decentralization can restrain environmental pollution, while excessive environmental decentralization aggravates environmental pollution. There is an inverted U-shaped relationship between environmental regulation and environmental pollution. If the intensity of environmental regulation is too low, it cannot inhibit environmental pollution, while if the intensity of environmental regulation is increased to a certain level, it can help to inhibit environmental pollution. The joint impact of environmental decentralization and environmental regulation cannot reduce environmental pollution. That is, with the enlargement of environmental decentralization, environmental regulation fails to reduce environmental pollution. The effect of environmental decentralization has significant regional heterogeneity in economic development level and emission intensity. The above conclusions have important reference value for optimizing the environmental decentralization system and formulating scientific environmental decentralization policies.