Commercial and sport fishes are subject to rigorous monitoring for concentrations of elements that could pose threats to human health, with numerous advisories issued by authorities annually for those fisheries with high mercury (Hg) concentrations. In Lake Winnipeg, Manitoba, Canada, the commercial walleye fishery is valued at more than $20 million/year, but has historically been subject to Hg advisories. We used an information theoretic approach to evaluate the utility of non-destructive fish-scale sampling to predict As, Mn and Hg concentrations, as well as stable isotope values in walleye muscle by analysing paired samples. Hg concentrations in scales were significantly related to those in muscle (r2 = 0.75), but the relationships were weaker for As and Mn. The δ15N values in scales predicted δ15N in muscle reasonably well (r2 = 0.72), whereas scale δ13C and δ34S had less predictive power for estimating their respective muscle stable isotope values. For all three isotope values, sex was a marginal predictor, with parameter confidence intervals bounding zero. Analytical constraints currently limit the utility of non-destructively analysing scales for Hg, but hindcasting trophic changes using archived walleye scales may be useful in understanding shifts in nutrients and production, particularly in impacted lake systems.