The Hai River Basin (HRB) is one of the most polluted river basins in China. The basin suffers from various types of pollutants including heavy metals and nutrients due to a high population density and rapid economic development in this area. We assessed the relationship between heavy metal accumulation by periphyton playing an important role in fluvial food webs and eutrophication in the HRB. The concentrations of the unicellular diatoms (type A), filamentous algae with diatoms (type B), and filamentous algae (type C) varied along the river, with type A dominating upstream, and types B then C increasing in concentration further downstream, and this was consistent with changes in the trophic status of the river. The mean heavy metal concentrations in the type A, B and C organisms were Cr: 18, 18 and 24 mg/kg, respectively, Ni: 9.2, 10 and 12 mg/kg, respectively, Cu: 8.4, 19 and 29 mg/kg, respectively, and Pb: 11, 9.8 and 7.1 mg/kg respectively. The bioconcentration factors showed that the abilities of the organisms to accumulate Cr, Ni and Pb decreased in the order type A, type B, then type C, but their abilities to accumulate Cu increased in that order. The Ni concentration was a good predictor of Cr, Cu and Pb accumulation by all three periphyton types. Our study shows that heavy metal accumulation by periphyton is associated with eutrophication in the rivers in the HRB.