Environmental DNA studies have proliferated over the last decade, with promising data describing the diversity of organisms inhabiting aquatic and terrestrial ecosystems. The recovery of DNA present in the sediment of aquatic systems (sedDNA) has provided short- and long-term data on a wide range of biological groups (e.g., photosynthetic organisms, zooplankton species) and has advanced our understanding of how environmental changes have affected aquatic communities. However, substantial challenges remain for recovering the genetic material of macro-organisms (e.g., fish) from sediments, preventing complete reconstructions of past aquatic ecosystems, and limiting our understanding of historic, higher trophic level interactions. In this review, we outline the biotic and abiotic factors affecting the production, persistence, and transport of fish DNA from the water column to the sediments, and address questions regarding the preservation of fish DNA in sediment. We identify sources of uncertainties around the recovery of fish sedDNA arising during the sedDNA workflow. This includes methodological issues related to experimental design, DNA extraction procedures, and the selected molecular method (quantitative PCR, digital PCR, metabarcoding, metagenomics). By evaluating previous efforts (published and unpublished works) to recover fish sedDNA signals, we provide suggestions for future research and propose troubleshooting workflows for the effective detection and quantification of fish sedDNA. With further research, the use of sedDNA has the potential to be a powerful tool for inferring fish presence over time and reconstructing their population and community dynamics.