Fish introduction and nutrient enrichment are two major environmental stressors for many freshwater lakes. Thus far, their ecological impacts have largely been evaluated independently, despite that fish invasion and predation may interact with lake trophic status. We examined paleoecological records from four large lakes of Southwest China to quantify the strength and interaction of icefish invasion and eutrophication in affecting zooplankton over time. There was a significant and positive relationship (P < 0.01) between sediment Chl a concentration and bosminid flux in each lake with bosminid size structure being greater in more productive lakes, indicating a strong bottom-up control. Furthermore, a consistent decrease in bosminid body sizes after fish introduction was found in Fuxian where icefish grew most successfully among our lakes. The variance partitioning results showed a decrease in the relative importance of planktivorous predation in driving zooplankton production with increased trophic status across lakes, with their joint effect showing a unimodal model in strength. In all, there was regional heterogeneity in the population status and ecological impact of invasive icefish that varied with lake trophic status over time. Therefore, nutrient status needs to be considered in assessing long-term ecological status and consequences of fish invasion in stressed freshwaters.