In southeastern Australia, the diet of long-nosed fur seals (Arctocephalus forsteri) includes seabirds. Populations of this recovering predator may correlate with declining little penguins (Eudyptula minor), a species of cultural and conservation concern. Such wildlife conflicts require robust quantitative data on predation incidence to appropriately assess risks. Using scats collected from multiple sites, we applied DNA and hard-parts analyses to estimate predation incidence, number of seabird species impacted and the relative importance of prey species to the predator. DNA metabarcoding identified more seabird taxa and multiple species within a sample, while parallel use of techniques revealed greater seabird taxa than either method alone. The frequency of occurrence of predation on seabirds ranged from 9.1–29.3% of samples and included up to six seabird taxa. While variable across sites, penguin predation was the most common, occurring in 6.1–25.3% of samples, higher than previously reported. Polymorphism analysis of the penguin DNA identified five distinct mitochondrial haplotypes representing 16 individuals (minimum) consumed across 10 scat samples. We recommend broader spatiotemporal sampling of predator diets to identify hotspots of concern for penguins. Recovering long-nosed fur seals constitute a success story for conservation, therefore anthropogenic threats require mitigation to protect the little penguins.