Based on the Chinese General Social Survey (CGSS) large-sample survey data, the impact of the public’s satisfaction of government environmental governance and the public participation effectiveness on government trust were empirically analyzed. It is found that the public’s satisfaction with the environmental governance of the central government (local government) has a significant positive impact on the trust of the central government (local government). However, the public’s satisfaction of the central government’s environmental governance has a significant negative impact on the trust of the local government. The study also shows that the process effectiveness and the result effectiveness of public participation have a significant positive impact on the trust of the central government and the trust of the local government respectively. Therefore, generally speaking, the improvement of the public’s satisfaction with the government’s environmental governance can enhance the government trust, but the relationship between the two is complex to some extent. Protecting the right of the public to participate effectively can enhance the trust of the governments, and “procedural justice” and “result justice” are both indispensable.