Hemiptera, the largest non-holometabolous order of insects, represents ~7% of metazoan diversity. With extraordinary life histories and highly specialized morphological adaptations, hemipterans have exploited diverse habitats and food sources through ~300 million years of evolution. To elucidate the phylogeny and evolutionary history of Hemiptera, we carried out the most comprehensive mitogenomics analysis on the richest taxon sampling to date covering all the suborders and infraorders, including 34 newly sequenced and 94 published mitogenomes. With optimized branch length and sequence heterogeneity, Bayesian analyses using a site-heterogeneous mixture model resolved the higher-level hemipteran phylogeny as: (Sternorrhyncha, (Auchenorrhyncha, (Coleorrhyncha, Heteroptera))). Ancestral character state reconstruction and divergence time estimation suggest that the success of true bugs (Heteroptera) is unlikely due to angiosperm coevolution, but rather key adaptive innovations (e.g., prognathous mouthpart, predatory behavior and hemelytron) facilitating multiple independent shifts among diverse feeding habits and multiple independent colonizations of aquatic habitats.