Lake of the Woods (LOW) is an international waterbody spanning the Canadian provinces of Ontario and Manitoba, and the U.S. state of Minnesota. In recent years, there has been a perception that water quality has deteriorated in northern regions of the lake, with an increase in the frequency and intensity of toxin-producing cyanobacterial blooms. However, given the lack of long-term data these trends are difficult to verify. As a first step, we examine spatial and seasonal patterns in water quality in this highly complex lake on the Canadian Shield. Further, we examine surface sediment diatom assemblages across multiple sites to determine if they track within-lake differences in environmental conditions. Our results show that there are significant spatial patterns in water quality in LOW. Principal Component Analysis divides the lake into three geographic zones based primarily on algal nutrients (i.e., total phosphorus, TP), with the highest concentrations at sites proximal to Rainy River. This variation is closely tracked by sedimentary diatom assemblages, with [TP] explaining 43% of the variation in diatom assemblages across sites. The close correlation between water quality and the surface sediment diatom record indicate that paleoecological models could be used to provide data on the relative importance of natural and anthropogenic sources of nutrients to the lake.