BACKGROUND: Evolutionary relationships among the 11 extant orders of insects that undergo complete metamorphosis, called Holometabola, remain either unresolved or contentious, but are extremely important as a context for accurate comparative biology of insect model organisms. The most phylogenetically enigmatic holometabolan insects are Strepsiptera or twisted wing parasites, whose evolutionary relationship to any other insect order is unconfirmed. They have been controversially proposed as the closest relatives of the flies, based on rDNA, and a possible homeotic transformation in the common ancestor of both groups that would make the reduced forewings of Strepsiptera homologous to the reduced hindwings of Diptera. Here we present evidence from nucleotide sequences of six single-copy nuclear protein coding genes used to reconstruct phylogenetic relationships and estimate evolutionary divergence times for all holometabolan orders. RESULTS: Our results strongly support Hymenoptera as the earliest branching holometabolan lineage, the monophyly of the extant orders, including the fleas, and traditionally recognized groupings of Neuropteroidea and Mecopterida. Most significantly, we find strong support for a close relationship between Coleoptera (beetles) and Strepsiptera, a previously proposed, but analytically controversial relationship. Exploratory analyses reveal that this relationship cannot be explained by long-branch attraction or other systematic biases. Bayesian divergence times analysis, with reference to specific fossil constraints, places the origin of Holometabola in the Carboniferous (355 Ma), a date significantly older than previous paleontological and morphological phylogenetic reconstructions. The origin and diversification of most extant insect orders began in the Triassic, but flourished in the Jurassic, with multiple adaptive radiations producing the astounding diversity of insect species for which these groups are so well known. CONCLUSION: These findings provide the most complete evolutionary framework for future comparative studies on holometabolous model organisms and contribute strong evidence for the resolution of the 'Strepsiptera problem', a long-standing and hotly debated issue in insect phylogenetics.