Recent studies have concluded that coal-tar-based pavement sealants are a major source of polycyclic aromatic hydrocarbons (PAHs) in urban settings in large parts of the United States. In 2006, Austin, TX, became the first jurisdiction in the U.S. to ban the use of coal-tar sealants. We evaluated the effect of Austin’s ban by analyzing PAHs in sediment cores and bottom-sediment samples collected in 1998, 2000, 2001, 2012, and 2014 from Lady Bird Lake, the principal receiving water body for Austin urban runoff. The sum concentration of the 16 EPA Priority Pollutant PAHs (∑PAH₁₆) in dated core intervals and surficial bottom-sediment samples collected from sites in the lower lake declined about 44% from 1998–2005 to 2006–2014 (means of 7980 and 4500 μg kg^–1, respectively), and by 2012–2014, the decline was about 58% (mean of 3320 μg kg^–1). Concentrations of ∑PAH₁₆ in bottom sediment from two of three mid-lake sites decreased by about 71 and 35% from 2001 to 2014. Concentrations at a third site increased by about 14% from 2001 to 2014. The decreases since 2006 reverse a 40-year (1959–1998) upward trend. Despite declines in PAH concentrations, PAH profiles and source-receptor modeling results indicate that coal-tar sealants remain the largest PAH source to the lake, implying that PAH concentrations likely will continue to decline as stocks of previously applied sealant gradually become depleted.