An increasing body of literature suggests that acceptance of environmental policy instruments tends to change along with increased experience of the same. Among the more popular examples of this are the growing number of congestion-pricing initiatives emerging around the world; in several cases the acceptability of these projects among the public has been relatively low before implementation, but then acceptance has increased as experience of the project has grown. The question is just how, and in particular, why? I.e., what is it really that experience does to people's propensity to accept initially quite unpopular measures? In this article we analyze how the relationship between political trust, policy-specific beliefs and public support for policy tools is moderated or affected by people's personal experiences of those policy tools. On the basis of the experience of previous research, we test the way in which policy-specific beliefs, institutional trust and the legitimacy of the political decision-making process affect public attitudes toward a policy tool. In addition—and consistent with other studies—we expect these effects to be significantly reduced post-implementation, as people gain first-hand experience of a policy tool. More specifically, we theorize that the often emphasized process legitimacy is only valid as a factor driving support before implementation, and that the effect of general institutional trust is replaced by the level of trust specific to the implementing institutions after the introduction of the policy tool. We tested these hypotheses using a natural experiment; i.e., by studying public attitudes toward the introduction of congestion fees in the Swedish city of Gothenburg both before and after their introduction. By doing so, we were able to comprehensively analyze both the drivers behind public sentiments toward congestion charges and how these mechanisms transform as people are exposed to the costs and benefits of the policy tool in practice. Among other things, we found that with regard to fairness and environmental effectiveness, there is a clear symmetry in our results. The level of acceptance increased most noticeably among those who experienced that the environment was improved by the implemented tax, or that the system turned out to be fairer than expected. However, the opposite is also the case. Thus, among those experiencing that the environment was not improved, or that the system appeared to be less fair than expected, the level of acceptance decreased significantly after implementation. These results may have important policy implications.