Reductions in external nutrient loading are central to the mitigation of cyanobacterial blooms, but internal nutrient cycling can alter the recovery time and influence the cyanobacterial community composition. We analysed 45 years of monitoring data from the shallow, polymictic Lake Müggelsee, Germany to examine how changing nutrient availability has influenced cyanobacterial community dynamics. External total nitrogen (TN) and total phosphorus (TP) loading to Lake Müggelsee declined by >80% over the monitoring period. However, internal phosphorus cycling resulted in a more rapid decline in in-lake nitrogen concentrations relative to phosphorus, leading to increasingly strong and prolonged nitrogen limitation. Contrary to the expectation that N₂ fixation would compensate for declining external nitrogen supply, N₂-fixing cyanobacteria of the order Nostocales declined in both absolute biomass and their contribution to the phytoplankton community. Total heterocyte concentration also reduced due to biomass reductions. Responses differed within the Nostocales: Dolichospermum was more strongly associated with low dissolved inorganic nitrogen conditions and a stable watercolumn, whereas Aphanizomenon was favoured under comparatively greater nitrogen availability and lower light. Increasing nitrogen limitation was also associated with changes in cyanobacterial phenology. In earlier periods, when summer dissolved inorganic nitrogen was more abundant, Nostocales and Microcystis frequently co-occurred. More recently, peak Microcystis biomass has declined and shifted later in the season, consistently occurring after peak Nostocales biomass, indicating an increasing reliance on internal nitrogen sources. These findings show that dual nutrient management of external sources can be effective at reducing cyanobacterial biomass by enforcing a rapid reduction in in-lake N concentration, leading to sustained N-limitation without the proliferation of N₂ fixing cyanobacteria.