Bark and ambrosia beetles (Curculionidae, Scolytinae) display a conspicuous diversity of unusual genetic and ecological attributes and behaviors. Reconstructing the evolution of Scolytinae, particularly the large and ecologically significant tribe Cryphalini (pygmy borers), has long been problematic. These challenges have not adequately been addressed using morphological characters, and previous research has used only DNA sequence data from small numbers of genes. Through a combination of anchored hybrid enrichment, low-coverage draft genomes, and transcriptomes, we addressed these challenges by amassing a large molecular phylogenetic dataset for bark and ambrosia beetles. The resulting DNA sequence data from 251 protein coding genes (114,276 bp of nucleotide sequence data) support inference of the first robust phylogeny of Scolytinae, with a special focus on the species rich tribe Cryphalini and its close relatives. Key strategies, including inbreeding mating systems and fungus farming, evolved repeatedly across Scolytinae. We confirm 12 of 16 hypothesized origins of fungus farming, 6 of 8 origins of inbreeding polygyny and at least 11 independent origins of a super-generalist host range. These three innovations are statistically correlated, but their appearance within lineages was not necessarily simultaneous. Additionally, the evolution of extreme host plant generalism often preceded, rather than succeeded, fungus farming. Of the high-diversity tribes of Scolytinae, only Xyleborini is monophyletic, Corthylini is paraphyletic and Cryphalini is highly polyphyletic. Cryphalini sensu stricto is part of a clade containing the genera Hypothenemus, Cryphalus and Trypophloeus, and the tribe Xyloterini. Stegomerus and Cryptocarenus (Cryphalini) are part of a clade otherwise containing all Corthylini. Several other genera, including Ernoporus and Scolytogenes (Cryphalini), make up a distantly related clade. Several of the genera of Cryphalini are also intermixed. For example, Cryphalus and Hypocryphalus are intermingled, as well as Ernoporicus, Ptilopodius and Scolytogenes. Our data are consistent with widespread polyphyly and paraphyly across Scolytinae and within Cryphalini, and provides new insights into the evolution of inbreeding mating systems and fungus farming in the species rich and ecologically significant weevil subfamily Scolytinae.