Marine fish from the North East Atlantic Ocean (NEAO) are nutrient rich and considered a valuable economic resource. However, marine fish are also a major dietary source of several contaminants, including persistent organic pollutants (POPs) and heavy metals. Using one of the world’s largest seafood datasets (n > 25,000 individuals), comprising 12 commercially important fish species collected during 2006–2019 in the NEAO, we assessed the co-occurrence of elements and POPs, and evaluated potential risks to human consumers. Several positive correlations between concentrations of mercury (Hg), dioxins, polychlorinated biphenyls (PCBs) and polybrominated diphenyl ethers (PBDEs) were observed. Concentrations of Hg, dioxins, PCBs and PBDEs increased from North to South and associations between marine sediment contamination, sea temperature, and fish Hg and POPs concentrations were identified using multi-linear regression (MLR) models. In general, Hg concentrations in fillet and liver of fish were positively associated with increases in both sediment contamination and sea temperature. POPs concentrations in both fillet and liver were positively associated with increases in sediment contamination, and only POPs concentrations in the liver of benthopelagic and demersal species were found to be positively correlated with sea temperature. Using a probabilistic approach to estimate human contaminant exposure from seafood, we showed that intake of pelagic species posed the highest risk of dioxins and dioxin-like PCBs (DL-PCBs) exposure, while intake of benthopelagic and demersal species posed the highest risk of Hg exposure. This study can serve as a model to further understand the distribution, co-occurrence, and trends of contaminants in seafood harvested from the NEAO and their potential risks to human consumers.