The introduction of salmonids into lakes of western North America for sport fishing is a widespread phenomenon. While numerous investigations have documented cascading trophic interactions upon the introduction of fish into naturally fishless systems, little research has been done to investigate the importance of natural fish status (fishless vs. fish bearing) in modulating historical food web response to dual forcing by bottom-up (resource regulation from nutrients) and top-down (planktivory from stocked fish) processes. We used the paleolimnological record to reconstruct food web changes in four lakes in interior British Columbia that have been stocked with rainbow trout since the early to mid-1900s. Analysis of pigments, diatoms, and Cladocera was undertaken in cores from all lakes. We predicted that if fish were important in structuring cladoceran abundance and composition, we would document a decline in the abundance of large daphnids post-stocking in our two naturally fishless lakes, and little change in the two fish-bearing lakes. Instead, we documented increased abundance of large daphnids after stocking in all lakes in the early to mid-1900s, a finding inconsistent with size-selective predation from planktivorous fish. Further, our data suggest that deep, low-oxygen refugia may be important in sustaining populations of large Daphnia, a process which was enhanced by increased nutrients and lake production according to sub-fossil diatom and pigment analyses. This study shows that fish stocking does not invariably result in a decrease in large-bodied Cladocera and that nutrients and lake type can modulate the response of invertebrate planktivores.