Stark contrasts in clade species diversity are reported across the tree of life and are especially conspicuous when observed in closely related lineages. The explanation for such disparity has often been attributed to the evolution of key innovations that facilitate colonization of new ecological niches. The factors underlying diversification in bees remain poorly explored. Bees are thought to have originated from apoid wasps during the Mid-Cretaceous, a period that coincides with the appearance of angiosperm eudicot pollen grains in the fossil record. The reliance of bees on angiosperm pollen and their fundamental role as angiosperm pollinators have contributed to the idea that both groups may have undergone simultaneous radiations. We demonstrate that one key innovation--the inclusion of foreign material in nest construction--underlies both a massive range expansion and a significant increase in the rate of diversification within the second largest bee family, Megachilidae. Basal clades within the family are restricted to deserts and exhibit plesiomorphic features rarely observed among modern bees, but prevalent among apoid wasps. Our results suggest that early bees inherited a suite of behavioural traits that acted as powerful evolutionary constraints. While the transition to pollen as a larval food source opened an enormous ecological niche for the early bees, the exploitation of this niche and the subsequent diversification of bees only became possible after bees had evolved adaptations to overcome these constraints.