The aim of the present study was to investigate algal–bacterial interactions in a gradient of metal contaminated natural sediments. By means of multivariate techniques, we related the genetic structure (denaturing gradient gel electrophoresis, DGGE) and the physiological structure (community-level physiological profiling, CLPP) of the bacterial communities to the species composition of the algal communities and to the abiotic environmental variables, including metal contamination. The results revealed that genetic and physiological structure of the bacterial communities correlated with the species composition of the algal community, but hardly to the level of metal pollution. This must be interpreted as an indication for a strong and species-specific linkage of algal and bacterial species in floodplain sediments. Metals were, however, not proven to affect either the algal or the bacterial communities of the Dutch river floodplains. Algal and bacterial communities in floodplain sediments are interlinked, but are not affected by metal pollution.