We applied DNA-based faecal analysis to determine the diet of female Australian sea lions (n = 12) from two breeding colonies in South Australia. DNA dietary components of fish and cephalopods were amplified using the polymerase chain reaction and mitochondrial DNA primers targeting the short (~100 base pair) section of the 16S gene region. Prey diversity was determined by sequencing ~50 amplicons generated from clone libraries developed for each individual. Faecal DNA was also combined and cloned from multiple individuals at each colony and fish diversity determined. Diets varied between individuals and sites. Overall, DNA analysis identified a broad diversity of prey comprising 23 fish and five cephalopod taxa, including many species not previously described as prey of the Australian sea lion. Labridae (wrasse), Monacanthidae (leatherjackets) and Mullidae (goat fish) were important fish prey taxa. Commonly identified cephalopods were Octopodidae (octopus), Loliginidae (calamary squid) and Sepiidae (cuttlefish). Comparisons of fish prey diversity determined by pooling faecal DNA from several samples provided a reasonable but incomplete resemblance (55–71%) to the total fish diversity identified across individual diets at each site. Interpretation of diet based on the recovery of prey hard-parts identified one cephalopod beak (Octopus sp.) and one fish otolith (Parapriacanthus elongatus). The present study highlights the value of DNA-based analyses and their capabilities to enhance information of trophic interactions.