We characterized spatial patterns of surface sediment concentrations of seven polychlorinated biphenyls (PCBs), seven polycyclic aromatic hydrocarbons (PAHs), three chlorinated pesticides, and five metals in Norwegian waters and Skagerrak. In total, we analyzed 5036 concentrations of 22 chemical substances that were measured between 1986 and 2014 at 333 sampling sites by means of generalized additive models (GAMs). We found that GAMs with organic carbon content of the sediment and latitude and longitude as co-variates explained as ca. 75% of the variability of the contaminant sediment concentrations. For metals, a predominantly hotspot-driven spatial pattern was found, i.e., we identified historical pollution hotspots (e.g., Sørfjord in western Norway) for mercury, zinc, cadmium, and lead. Highest concentrations of PAHs and PCBs were found close to densely populated and industrialized regions, i.e., in the North Sea and in the Kattegat and Skagerrak. The spatial pattern of the PCBs suggests the secondary and diffuse atmospheric nature of their sources. Atmospheric inputs are the main sources of pollution for most organic chemicals considered, but north of the Arctic circle, we found that concentrations of PAHs increased from south to north most likely related to a combination of coal-eroding bedrock and the biological pump. The knowledge acquired in the present research is essential for developing effective remediation strategies that are consistent with international conventions on pollution control.