As carcinogenic and pervasive pollutants, polycyclic aromatic hydrocarbons (PAHs) in surface water are crucial to environmental policies, and the understanding of their trends and influencing factors is critical for achieving a good chemical and ecological status of water bodies. Based on long-term monitoring data from 1998 to 2017, this study systematically evaluated the spatiotemporal distribution, multimedia transport, fate, and source apportionment of PAHs adsorbed on suspended particulate matter (SPM) in Rhine and Elbe Rivers. The results of the Mann-Kendall test indicated that pollution levels of PAHs decreased from 2.81×10⁵μg⋅s⁻¹ to 9.80×10⁴μg⋅s⁻¹ on average in the Rhine and from 1.60×10⁵ μg⋅s⁻¹ to 5.21×10⁴ μg⋅s⁻¹ in the Elbe in the last 20 years. Spatially, SPM near urban areas had higher PAH mass fluxes (Rhine:3.07×10⁵μg⋅s⁻¹, Elbe: 1.73×10⁵μg⋅s⁻¹) and greater rates of decrease (slopes for Rhine and Elbe: −409, −323) than those near rural areas (Rhine:1.41×10⁵ μg⋅s⁻¹, Elbe: 9.35×10⁴μg⋅s⁻¹; slopes for Rhine and Elbe: −128, −89), indicating the significant influence of anthropogenic activities. Wavelet analysis showed that the pollution level of PAH had significant periodic oscillations for the Rhine and Elbe, and revealed several abrupt change points for the two rivers. A multimedia fugacity model demonstrated that impervious surfaces had the highest concentration (Rhine: 1.84g⋅m⁻³, Elbe: 0.15g⋅m⁻³), while soil (Rhine: 8.33×10⁷g, Elbe: 2.53×10⁶g) and sediments (Rhine: 4.85×10⁶g, Elbe: 1.31×10⁶g) had higher masses of PAHs. Furthermore, source apportionment computed using a self-organizing map and positive matrix factorization model suggested that the major sources of PAHs were vehicular emissions and coal combustion, which accounted for 51.86% of the total mass in the Rhine and 62.92% in the Elbe. The data revealed that the long-term trends of PAH variation were associated with changes in energy consumption and the implementation of vehicular emission standards. Therefore, the substitution of coal and petroleum with renewable energies could assist strategies of PAH mitigation in the environment and gradual reduction of pollution levels.