Over decades, large amounts of the neurotoxin lead were released into the European environment, mostly from gasoline lead additives. Emissions were growing unabatedly until the 1970s, when a series of regulations on the allowed gasoline lead content were adopted. As a result, in the 1990s most gasoline contained only small amounts of lead. We have examined this case of environmental pollution and regulation, and performed a retrospective assessment of the extent of regional-scale lead pollution and the effects of gasoline lead regulations in Europe. With the help of a regional climate model, NCEP re-analyses, spatially disaggregated lead emissions from road traffic and point sources, and various local data, the airborne pathways and depositions of gasoline lead in Europe since 1958 were reconstructed. It turns out that this approach is successful in describing the time-variable, spatially disaggregated deposition of gasoline lead. Additional data from analyses of concentrations in biota, including plant leaves, mussels and human blood, allows an assessment about the impact of the lead phase-out on the quality of the environment. Demonstrating the success of the lead policies, concentrations in leaves and human blood have steadily declined since the early 1980s. At the same time, the economic repercussions that had been feared did not emerge. Instead, the affected mineral oil and car manufacturing industries in Germany (our case-study) were able to deal with the effort without incurring significant extra costs. We suggest that our method of quantitatively reconstructing and anticipating fluxes and depositions of substances can be applied to other relevant substances as well, such as, for example, Persistent Organic Pollutants, radioactive substances or pollens.