Classification and evolutionary studies of particularly speciose clades pose important challenges, as phylogenetic analyses typically sample a small proportion of the existing diversity. We examine here one of the largest bee genera, the genus Megachile - the dauber and leafcutting bees. Besides presenting a phylogeny based on five nuclear genes (5480 aligned nucleotide positions), we attempt to use the phylogenetic signal of mitochondrial DNA barcodes, which are rapidly accumulating and already include a substantial proportion of the known species diversity in the genus. We used barcodes in two ways: first, to identify particularly divergent lineages and thus to guide taxon sampling in our nuclear phylogeny; second, to augment taxon sampling by combining nuclear markers (as backbone for ancient divergences) with DNA barcodes. Our results indicate that DNA barcodes bear phylogenetic signal limited to very recent divergences (3-4 my before present). Sampling within clades of very closely related species may be augmented using this technique, but our results also suggest statistically supported, but incongruent placements of some taxa. However, the addition of one single nuclear gene (LW-rhodopsin) to the DNA barcode data was enough to recover meaningful placement with high clade support values for nodes up to 15 million years old. We discuss different proposals for the generic classification of the tribe Megachilini. Finding a classification that is both in agreement with our phylogenetic hypotheses and practical in terms of diagnosability is particularly challenging as our analyses recover several well-supported clades that include morphologically heterogeneous lineages. We favour a classification that recognizes seven morphologically well-delimited genera in Megachilini: Coelioxys, Gronoceras, Heriadopsis, Matangapis, Megachile, Noteriades and Radoszkowskiana. Our results also lead to the following classification changes: the groups known as Dinavis, Neglectella, Eurymella and Phaenosarus are reestablished as valid subgenera of the genus Megachile, while the subgenus Alocanthedon is placed in synonymy with M. (Callomegachile), the subgenera Parachalicodoma and Largella with M. (Pseudomegachile), Anodonteutricharaea with M. (Paracella), Platysta with M. (Eurymella), and Grosapis and Eumegachile with M. (Megachile) (new synonymies). In addition, we use maximum likelihood reconstructions of ancestral geographic ranges to infer the origin of the tribe and reconstruct the main dispersal routes explaining the current, cosmopolitan distribution of this genus.