Technical Abstract: Megachilidae is the second largest bee family containing more than 4000 described species worldwide in two subfamilies and seven extant tribes; it also includes a few morphologically distinctive extinct lineages from the middle Eocene: one tribe (Protolithurgini) and two subtribes presently in the Osmiini (Glyptapina and Ctenoplectrellina). Megachilidae consists of both parasitic and solitary free-living species, some of them ecologically and economically important pollinators. Phylogenetic relationships within this family are poorly understood. The monophyly of the subfamily Fideliinae is questionable, the relationships among the tribes and subtribes in the subfamily Megachilinae are unknown, and some extant genera cannot be placed with certainty at the tribal level. Using a cladistic analysis of adult external morphological characters, we explore the relationships of the eight tribes and two subtribes currently recognized in Megachilidae. Our dataset included 80% of the extant generic-level diversity, representatives of all fossil taxa, and was analyzed using parsimony. We employed 200 characters and selected seven outgroups and 72 ingroup species of 60 genera, plus seven species of four extinct genera from Baltic amber. Our analysis shows that Fideliinae and the tribes Anthidiini and Osmiini of Megachilinae are paraphyletic; it supports the monophyly of Megachilinae, including the extinct taxa, and the sister group relationship of Lithurgini to the remaining megachilines. The Sub-Saharan genus Aspidosmia, a rare group with a mixture of osmiine and anthidiine features, is herein removed from Anthidiini and placed in its own tribe, Aspidosmiini Gonzalez & Griswold, new tribe. Protolithurgini is the sister of Lithurgini, both placed herein in the subfamily Lithurginae; the other extinct taxa, Glyptapina and Ctenoplectrellina, are more basally related among Megachilinae than Osmiini, near Aspidosmia, and are herein treated at the tribal level. Noteriades, a genus presently in the Osmiini, is herein transferred to the Megachilini. Thus, we recognize four subfamilies (Fideliinae, Pararhophitinae, Lithurginae, and Megachilinae) and nine tribes in Megachilidae. We briefly discuss the evolutionary history and biogeography of the family, present alternative classifications, and provide a revised key to the extant tribes of Megachilinae.