To trace the evolution of host-plant choice in bees of the genus Chelostoma (Megachilidae), we assessed the host plants of 35 Palearctic, North American and Indomalayan species by microscopically analyzing the pollen loads of 634 females and reconstructed their phylogenetic history based on four genes and a morphological dataset, applying both parsimony and Bayesian methods. All species except two were found to be strict pollen specialists at the level of plant family or genus. These oligolectic species together exploit the flowers of eight different plant orders that are distributed among all major angiosperm lineages. Based on ancestral state reconstruction, we found that oligolecty is the ancestral state in Chelostoma and that the two pollen generalists evolved from oligolectic ancestors. The distinct pattern of host broadening in these two polylectic species, the highly conserved floral specializations within the different clades, the exploitation of unrelated hosts with a striking floral similarity as well as a recent report on larval performance on nonhost pollen in two Chelostoma species clearly suggest that floral host choice is physiologically or neurologically constrained in bees of the genus Chelostoma. Based on this finding, we propose a new hypothesis on the evolution of host range in bees.