Lake of the Woods (LOW) is a large, morphologically and hydrologically complex lake of international importance, located in the provinces of Ontario and Manitoba and the state of Minnesota. A high-resolution sedimentary sequence retrieved near Kenora, Ontario, and spanning at least the past ~11,000 cal yr BP (calibrated years before present), was analysed for multiple environmental proxies with an emphasis on diatom assemblage composition and spectrally-inferred chlorophyll a. These biological proxies indicate that northern LOW was relatively nutrient-rich soon after its isolation from glacial Lake Agassiz ~10,000 cal yr BP. The post-glacial hydrological and environmental history of LOW was found to be controlled by both climate and isostatic rebound. During the low water phase of the mid-Holocene dry and warm period, abrupt and synchronous shifts across all proxies suggest that the northern basin had a relatively deep and well-mixed water column that experienced increases in nutrients and whole-lake algal production. This differs from recent limnological changes associated with warming since the late-1970s, where primary production increased concurrently with large shifts in diatoms indicative of increased thermal stability, but with little change in nutrients. The millennial-scale context of this study provides evidence that climate has long played an important role in algal dynamics in LOW, with implications for lake management strategies concerning recent increases in nuisance algal blooms on LOW.