Insect diversity represents about 60% of the estimated million-and-a-half described eukaryotic species worldwide, yet comprehensive and well-resolved intra-ordinal phylogenies are still lacking for the majority of insect groups. This is the case especially for the most species-rich insect group, the beetles (Coleoptera), a group for which less than 4% of the known species have had their DNA sequenced. In this study, we reconstruct the first higher level phylogeny based on DNA sequence data for the species-rich darkling beetles, a family comprising at least 20000 species. Although amongst all families of beetles Tenebrionidae ranks seventh in terms of species diversity, the lack of knowledge on the phylogeny and systematics of the group is such that its monophyly has been questioned (not to mention those of the subfamilies and tribes contained within it). We investigate the evolutionary history of Tenebrionidae using multiple phylogenetic inference methods (Bayesian inference, maximum likelihood and parsimony) to analyse a dataset consisting of eight gene fragments across 404 taxa (including 250 tenebrionid species). Although the resulting phylogenetic framework only encompasses a fraction of the known tenebrionid diversity, it provides important information on their systematics and evolution. Whatever the methods used, our results provide strong support for the monophyly of the family, and highlight the likely paraphyletic or polyphyletic nature of several important tenebrionid subfamilies and tribes, notably the polyphyletic subfamilies Diaperinae and Tenebrioninae that clearly require substantial revision in the future. Some interesting associations in several groups are also revealed by the phylogenetic analyses, such as the pairing of Aphtora Bates with Phrenapatinae. Furthermore this study advances our knowledge of the evolution of the group, providing novel insights into much-debated theories, such as the apparent relict distribution of the tribe Elenophorini.