Phylogenetic relationships of dung beetles in the tribe Onthophagini, including the species-rich, cosmopolitan genus Onthophagus, were inferred using whole mitochondrial genomes. Data were generated by shotgun sequencing of mixed genomic DNA from >100 individuals on 50% of an Illumina MiSeq flow cell. Genome assembly of the mixed reads produced contigs of 74 (nearly) complete mitogenomes. The final dataset included representatives of Onthophagus from all biogeographic regions, closely related genera of Onthophagini, and the related tribes Onitini and Oniticellini. The analysis defined four major clades of Onthophagini, which was paraphyletic for Oniticellini, with Onitini as sister group to all others. Several (sub)genera considered as members of Onthophagus in the older literature formed separate deep lineages. All New World species of Onthophagus formed a monophyletic group, and the Australian taxa are confined to a single or two closely related clades, one of which forms the sister group of the New World species. Dating the tree by constraining the basal splits with existing calibrations of Scarabaeoidea suggests an origin of Onthophagini sensu lato in the Eocene and a rapid spread from an African ancestral stock into the Oriental region, and secondarily to Australia and the Americas at about 20–24 Mya. The successful assembly of mitogenomes and the well-supported tree obtained from these sequences demonstrates the power of shotgun sequencing from total genomic DNA of species pools as an efficient tool in genus-level phylogenetics.