The ecological integrity of freshwater lakes is influenced by atmospheric and riverine deposition of contaminants, shoreline development, eutrophication, and the introduction of non-native species. Changes to the trophic structure of Lake Winnipeg, Canada, and consequently, the concentrations of contaminants and trace elements measured in tissues of native fishes, are likely attributed to agricultural runoff from the 977,800 km2 watershed and the arrival of non-native zooplankters and fishes. We measured δ13C, δ15N, and δ34S along with concentrations of 15 trace elements in 17 native fishes from the north and south basins of Lake Winnipeg in 2009 and 2010. After adjusting for differences in isotopic baseline values between the two basins, fishes in the south basin had consistently higher δ13C and δ34S, and lower δ15N. We found little evidence of biomagnification of trace elements at the community level, but walleye (Sander vitreus) and freshwater drum (Aplodinotus grunniens) had higher mercury and selenium concentrations with increased trophic position, coincident with increased piscivory. There was evidence of growth dilution of cobalt, copper, manganese, molybdenum, thallium, and vanadium, and bioaccumulation of mercury, which could be explained by increases in algal (and consequently, lake and fish) productivity. We conclude that the north and south basins of Lake Winnipeg represent very different communities with different trophic structures and trace element concentrations.