Lake of the Woods (LOW) is a large, transboundary lake that straddles the provinces of Ontario and Manitoba, and the state of Minnesota. Although algal blooms have been reported in the lake since the early 1800s, monitoring data and anecdotal evidence suggest that toxic, cyanobacterial blooms have increased in frequency and intensity in recent years. However, total phosphorus inputs from the lake's primary tributary, the Rainy River, have declined significantly since the late 1960s. We explore this disconnect by examining spectrally-inferred determinations of chlorophyll a (Chl-a) in lake sediment cores, as a measure of past changes in aquatic primary production. Beginning in the late 1970s to early 1980s, inferred Chl-a increased at 5 impact sites in the north end of LOW that currently experience cyanobacterial blooms in late summer and autumn. In contrast, no change in Chl-a was observed at an oligotrophic reference site with much lower cyanobacteria biomass. At the impact sites, Chl-a generally showed no significant relationship to long-term trends in diatom-inferred total phosphorus concentrations, but was significantly and positively correlated to climatic variables, including mean annual air temperature at all sites and total annual precipitation at 4 sites. These data suggest that climate change may exacerbate algal blooms in this moderately-enriched lake. The results also show that the effects of climate change on aquatic production may be enhanced at sites with higher nutrient concentrations, likely because of positive feedbacks between cyanobacteria biomass, water temperature and nutrient availability. The impact of climate change should be considered carefully in future management initiatives.