Frame Lake, located within the city of Yellowknife, Northwest Territories, Canada, has been identified as requiring significant remediation due to its steadily declining water quality and inability to support fish by the 1970s. Former gold mining operations and urbanization around the lake have been suspected as probable causes for the decline in water quality. While these land-use activities are well documented, little information is available regarding their impact on the lake itself. For this reason, Arcellinida, a group of shelled protozoans known to be reliable bioindicators of land-use change, were used to develop a hydroecological history of the lake. The purpose of this study was to use Arcellinida to: (1) document the contamination history of the lake, particularly related to arsenic (As) associated with aerial deposition from mine roaster stacks; (2) track the progress of water quality deterioration in Frame Lake related to mining, urbanization and other activities; and (3) identify any evidence of natural remediation within the lake. Arcellinida assemblages were assessed at 1-cm intervals through the upper 30 cm of a freeze core obtained from Frame Lake. The assemblages were statistically compared to geochemical and loss-on-ignition results from the core to document the contamination and degradation of conditions in the lake. The chronology of limnological changes recorded in the lake sediments were derived from 210Pb, 14C dating and known stratigraphic events. The progress of urbanization near the lake was tracked using aerial photography. Using Spearman correlations, the five most significant environmental variables impacting Arcellinida distribution were identified as minerogenics, organics, As, iron and mercury (p < 0.05; n = 30). Based on CONISS and ANOSIM analysis, three Arcellinida assemblages are identified. These include the Baseline Limnological Conditions Assemblage (BLCA), ranging from 17–30 cm and deposited in the early Holocene >7,000 years before present; the As Contamination Assemblage (ACA), ranging from 7–16 cm, deposited after ∼1962 when sedimentation began in the lake again following a long hiatus that spanned to the early Holocene; and the Eutrophication Assemblage (EA), ranging from 1–6 cm, comprised of sediments deposited after 1990 following the cessation of As and other metal contaminations. The EA developed in response to nutrient-rich waters entering the lake derived from the urbanization of the lake catchment and a reduction in lake circulation associated with the development at the lake outlet of a major road, later replaced by a causeway with rarely open sluiceways. The eutrophic condition currently charactering the lake—as evidenced by a population explosion of eutrophication indicator taxa Cucurbitella tricuspis—likely led to a massive increase in macrophyte growth and winter fish-kills. This ecological shift ultimately led to a system dominated by Hirudinea (leeches) and cessation of the lake as a recreational area.