DNA-based techniques have proven useful for defining trophic links in a variety of ecosystems and recently developed sequencing technologies provide new opportunities for dietary studies. We investigated the diet of Australian fur seals (Arctocephalus pusillus doriferus) by pyrosequencing prey DNA from faeces collected at three breeding colonies across the seals’ range. DNA from 270 faecal samples was amplified with four polymerase chain reaction primer sets and a blocking primer was used to limit amplification of fur seal DNA. Pooled amplicons from each colony were sequenced using the Roche GS-FLX platform, generating > 20 000 sequences. Software was developed to sort and group similar sequences. A total of 54 bony fish, 4 cartilaginous fish and 4 cephalopods were identified based on the most taxonomically informative amplicons sequenced (mitochondrial 16S). The prevalence of sequences from redbait (Emmelichthys nitidus) and jack mackerel (Trachurus declivis) confirm the importance of these species in the seals’ diet. A third fish species, blue mackerel (Scomber australasicus), may be a more important prey species than previously recognised. There were major differences in the proportions of prey DNA recovered in faeces from different colonies, probably reflecting differences in prey availability. Parallel hard-part analysis identified largely the same main prey species as did the DNA-based technique, but with lower species diversity and no remains from cartilaginous prey. The pyrosequencing approach presented significantly expands the capabilities of DNA-based methods of dietary analysis and is suitable for large-scale diet investigations on a broad range of animals.