Carbon and nitrogen stable isotope ratios are increasingly used to study long-term change in food web structure and nutrient cycling. We retrospectively analyse elemental composition (C, N and P) and stable isotopes (δ 13C, δ 15N) in archived monitoring samples of two important taxa from the bottom of the food web; the filamentous ephemeral macroalgae Cladophora spp. and the blue mussel Mytilus edulis trossulus from three contrasting regions in the Baltic Sea (coastal Bothnian Sea and Baltic Proper, open sea central Baltic). The aim is to statistically link the observed spatial and interannual (8–24 years’ time-series) variability in elemental and isotope baselines with their biomass trends and to the oceanographic monitoring data reflecting the ongoing environmental changes (i.e., eutrophication and climate) in this system. We find clear differences in isotope baselines between the two major Baltic Sea basins. However, the temporal variation in Mytilus δ 13C was similar among regions and, at the open sea station, mussels and algae δ 13C also correlated over time, likely reflecting a global (Suess) effect, whereas δ 15N of both taxa varied with local and regional dissolved nitrogen concentrations in water. δ 15N in source amino acids allowed detection of diazotrophic N in Mytilus, which was masked in bulk δ 15N. Finally, Cladophora N:P reflected regional nutrient levels in the water while P%, which differed for both taxa, was linked to food quality for Mytilus. This study highlights the potential of a multi-taxa and multi-stable isotope approach to understand nutrient dynamics and monitor long-term environmental changes.