Introduced trout can induce trophic cascades, however, a lack of pre-introduction data limits knowledge on their impact in many lakes. Traditional paleolimnological approaches have been used to study historic species changes, but until recently these have been restricted to taxa with preservable body-parts. To explore the ecosystem effects of Salmo trutta (brown trout) introduction on an oligotrophic lake in Aotearoa-New Zealand, we used a multi-marker sedimentary environmental DNA (sedDNA) approach coupled with pigments to detect changes across multiple trophic levels. DNA was extracted from core depths capturing approximately 100 years before and after the expected arrival of S. trutta, and metabarcoding was undertaken with four primer sets targeting the 12S rRNA (fish), 18S rRNA (eukaryotes) and cytochrome c oxidase (COI; eukaryotes) genes. The earliest detection of S. trutta eDNA was 1906 (1892–1919 CE with 95% high probability density function) suggesting their introduction was shortly before this. Native fish diversity (12S and 18S rRNA) decreased after the detection of S. trutta, albeit the data was patchy. A shift in overall eukaryotic and algal communities (18S rRNA and COI) was observed around 1856 (1841–1871 CE) to 1891 (1877–1904 CE), which aligns with the expected S. trutta introduction. However, taxonomy could not be assigned to many of the 18S rRNA and COI sequences. Pigment concentrations did not change markedly after S. trutta introduction. SedDNA provides a new tool for understanding the impact of disturbances such as the introduction of non-native species; however, there are still several methodological challenges to overcome.